区间DP 这题也是看着别人的代码写下来的 效果也不是很大 鄙视下自己 主要是自己作业还没做完 心急了一点 还被人催着做C#实验 有空写一下记忆化搜索版本
区间DP一般都是dp[l][r] 表示l到r这段区域的最优值 然后区间逐渐扩大 可以写成递推的 也可以记忆化搜索
这题还要加一维 代表当前的位置实在区间的最左边还是最右边
dp[l][r][0]代表在最左边l的位置 可以从dp[l+1][r][1]的状态从r 到l 或者 从dp[l+1][r][0]的状态从l+1到l
dp[l][r][1]代表在最右边r的位置 可以从dp[l][r-1][1]的状态从r-1 到r 或者 从dp[l][r-1][0]的状态从l 到r
然后注意每次那个值不是会增长的吗 要在当前的情况算进去 比如现在从l到r经过了x单位时间 那么要加上1到l-1 r+1到n这两段的增长值 这点比较抽象 也是难点
v先不考虑 最后乘上 做的时候 把v当作1来做
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define INF 1100000000 const int maxn = 1010; long long dp[maxn][maxn][2]; long long sum[maxn]; struct node { int x, y; }a[maxn]; bool cmp(node a, node b) { return a.x < b.x; } int main() { int n, v, x; while(scanf("%d %d %d", &n, &v, &x) != EOF) { for(int i = 1; i <= n; i++) scanf("%d %d", &a[i].x, &a[i].y); n++; a[n].x = x; a[n].y = 0; sort(a+1, a+n+1, cmp); int p; for(int i = 1; i <= n; i++) if(a[i].x == x) p = i; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dp[i][j][0] = dp[i][j][1] = INF; for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i].y; dp[p][p][0] = dp[p][p][1] = 0; for(int i = p; i >= 1; i--) { for(int j = p; j <= n; j++) { if(i == j) continue; int s1 = sum[i-1]; int s2 = sum[n]-sum[j]; if(s1 < 0) s1 = 0; if(s2 < 0) s2 = 0; int s = s1 + s2; dp[i][j][0] = min(dp[i][j][0], dp[i+1][j][0]+(long long)(a[i+1].x-a[i].x)*(s+a[i].y)); dp[i][j][0] = min(dp[i][j][0], dp[i+1][j][1]+(long long)(a[j].x-a[i].x)*(s+a[i].y)); dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][0]+(long long)(a[j].x-a[i].x)*(s+a[j].y)); dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][1]+(long long)(a[j].x-a[j-1].x)*(s+a[j].y)); //printf("%I64d %d %I64d\n", dp[i][j][1], i, dp[i][j-1][1]+(__int64)(a[j].x-a[j-1].x)*(s+a[j].y)); } } long long ans = min(dp[1][n][0], dp[1][n][1]); printf("%lld\n", ans*(long long)v); } return 0; }
ZOJ 3469 Food Delivery / 区间DP,布布扣,bubuko.com
原文:http://blog.csdn.net/u011686226/article/details/22303699