这是一道区间动态规划题
项目 | 分析 |
---|---|
状态 | $dp[l][r][k]$,代表关掉$l \sim r$区间所有灯且在左端点($k=0$),右端点($k=1$) |
阶段 | 区间的长度len |
决策 | $dp[l][r][0]=min(dp[l+1][r][0]+cost(左),dp[l+1][r][1]+cost(右)$(右端点略) |
边界 | $dp[c][c][0]=dp[c][c][1]=0$(起始点瞬间关灯) |
答案 | $min(dp[1][n][0],dp[1][n][1])$ |
参考代码:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 51;
int n,c;
int poss[MAXN],engs[MAXN];
int dp[MAXN][MAXN][2];
int cost(int a, int b, int l, int r) {
return (poss[a] - poss[b]) * (engs[n] + engs[l] - engs[r]);
}
int main() {
ios::sync_with_stdio(false);
memset(dp, 0x3F3F3F, sizeof(dp));
cin >> n >> c;
int x;
for ( int i = 1; i <= n; ++i ) {
cin >> poss[i] >> x;
engs[i] = engs[i - 1] + x;
}
dp[c][c][0] = dp[c][c][1] = 0;
for ( int len = 2; len <= n; ++len )
for ( int i = 1; i <= n - len + 1; ++i ) {
int l = i;
int r = i + len - 1;
dp[l][r][0] = min(dp[l + 1][r][0] + cost(l + 1, l, l, r),dp[l + 1][r][1] + cost(r, l, l, r));
dp[l][r][1] = min(dp[l][r - 1][0] + cost(r, l, l - 1, r - 1), dp[l][r - 1][1] + cost(r, r - 1, l - 1, r - 1));
}
cout << min(dp[1][n][0], dp[1][n][1]) << endl;
return 0;
}
边界处理有些繁琐,需要细心仔细。
拓展与思考:
要是关灯的时间各不相同呢?