区间dp,和UVa #1336 Fixing the Great Wall (例题9-21)类似。但数据规模太大,记忆化搜索会TLE,必须递推。
我一开始把状态设计为dp(i,j,k)表示当前已访问区间为[i,j],且站在 i (k == 0)或 j (k==1),最少还需多少时间收集全部宝藏。同时还需要一个辅助数组来记录当前已经经历的时间,来判断是否过了deadline。这个设计很臃肿。并且用记忆化搜索还行,但是递推就完全无能为力,因为无法判断到达某一宝藏时,是否已经过了deadline。
可以用对称的设计:dp(i,j,k)表示最短需要多少时间到达 [i,j,k]。对于所有的 i == j 的情况,dp值都为0,因为我们可以选择从这一点出发。状态的转移和上面的设计一样,都与#1336相同。
另外递推的时候,我习惯外层用diff从0到n-1表示i和j的差,但是TLE了。改成Rujia在书里用过的方法:i从n-1到0,j从i到n-1,就可以将时间缩短一半。
Run Time: 2.202s
#define UVa "9-8.1632.cpp" //Alibaba char fileIn[30] = UVa, fileOut[30] = UVa; #include<cstring> #include<cstdio> #include<algorithm> using namespace std; //Global Variables. Reset upon Each Case! const int maxn = 10000 + 5, INF = 1<<30, LEFT = 0, RIGHT = 1; int n, d[maxn][maxn][2], x[maxn], ddl[maxn]; ///// int main() { while(scanf("%d", &n) != EOF) { for(int i = 0; i < n; i ++) scanf("%d%d", &x[i], &ddl[i]); for(int i = n-1; i >= 0; i --) { for(int j = i; j < n; j ++) { int& u1 = d[i][j][LEFT]; int& u2 = d[i][j][RIGHT]; if(i == j) u1 = u2 = 0; else { u1 = u2 = INF; u1 = min(d[i+1][j][RIGHT] + x[j]-x[i], d[i+1][j][LEFT] + x[i+1]-x[i]); if(u1 >= ddl[i]) u1 = INF; u2 = min(d[i][j-1][LEFT] + x[j]-x[i], d[i][j-1][RIGHT] + x[j]-x[j-1]); if(u2 >= ddl[j]) u2 = INF; } } } int ans = min(d[0][n-1][0], d[0][n-1][1]); if(ans >= INF) printf("No solution\n"); else printf("%d\n", ans); } return 0; }