这道题是宁波集训的那道题，讲课时轻描淡写吧（应该是我听课不认真罢了），所以这样就要靠自己的理解了，
dp[i][j][0]表示从左端点开始完成整个区间的最小花费dp[i][j][1]表示从右端点开始完成整个区间的最小花费，就是这样的。
然后记录前驱，因为每次只会从端点开始，不然返回端点的时间是不必要的，这样就可以了，然后最后输出即可。
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 #include<cmath> 5 #include<cstring> 6 using namespace std; 7 8 const int NN=207,INF=1e9+7; 9 10 int n; 11 int t[NN],d[NN]; 12 int f[NN][NN][2],fa[NN][NN][2]; 13 14 int main() 15 { 16 while (~scanf("%d",&n)) 17 { 18 memset(f,0,sizeof(0)); 19 memset(fa,0,sizeof(fa)); 20 for (int i=1;i<=n;i++) 21 scanf("%d",&t[i]); 22 for (int i=1;i<=n;i++) 23 scanf("%d",&d[i]); 24 memset(f,0,sizeof(f)); 25 for (int k=2;k<=n;k++) 26 { 27 for (int i=1;i+k-1<=n;i++) 28 { 29 int j=i+k-1; 30 if (f[i+1][j][0]+d[i+1]-d[i]<f[i+1][j][1]+d[j]-d[i]) 31 { 32 f[i][j][0]=f[i+1][j][0]+d[i+1]-d[i]; 33 fa[i][j][0]=0; 34 } 35 else 36 { 37 f[i][j][0]=f[i+1][j][1]+d[j]-d[i]; 38 fa[i][j][0]=1; 39 } 40 if (f[i][j][0]>=t[i]||f[i][j][0]>INF) f[i][j][0]=INF;//没什么大不了的，防止溢出。 41 if (f[i][j-1][1]+d[j]-d[j-1]<f[i][j-1][0]+d[j]-d[i]) 42 { 43 f[i][j][1]=f[i][j-1][1]+d[j]-d[j-1]; 44 fa[i][j][1]=1; 45 } 46 else 47 { 48 f[i][j][1]=f[i][j-1][0]+d[j]-d[i]; 49 fa[i][j][1]=0; 50 } 51 if (f[i][j][1]>=t[j]||f[i][j][1]>INF) f[i][j][1]=INF;//没什么大不了的，防止溢出。 52 } 53 } 54 int l,r,w; 55 if (f[1][n][0]<INF) 56 { 57 printf("1"); 58 l=2,r=n,w=fa[1][n][0]; 59 } 60 else if (f[1][n][1]<INF) 61 { 62 printf("%d",n); 63 l=1,r=n-1,w=fa[1][n][1]; 64 } 65 else 66 { 67 printf("Mission Impossible "); 68 continue; 69 } 70 while (l<=r) 71 { 72 if (w==0) 73 { 74 printf(" %d",l); 75 w=fa[l][r][0],l++; 76 } 77 else 78 { 79 printf(" %d",r); 80 w=fa[l][r][1],r--; 81 } 82 } 83 printf(" "); 84 } 85 }