http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3541
题意：
有一排开关，有个开关有两个值t和d，t是按下开关后在t秒后会自动弹起，d为距离最左端点的距离。问是否能找到一个按开关的顺序使得在某一时刻所有开关都打开。
思路：
首先要找一个最优子结构性质。
对于区间【l，r】来说，我们可以从任意一点出发，现在如果我们从中间的一点出发，那么必然要先去一个端点，然后再去另一个端点，那么在这个过程中，有些开关可能会经过多次，比如从出发点去左端点的过程中，可以打开路上的开关，但是我们还必须去右端点，那么在去右端点的路上，这些开关又会经过，此时又可以打开它，那么晚按肯定比早按来得更好，也就是说，从端点出发和从中间任意一点出发的效果是一样的，但是更省时间，这样一来，对于区间【l，r】，肯定是从端点出发的。
这样一来，用d【l】【r】【0/1】表示从左/右端点出发打开所有开关所需的最少时间。
如果从左端点出发，然后t【l】<=d【l】【r】【0/1】，那么就说明此时是无法打开区间内的所有开关的。
同时记录好路径即可。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef long long ull; 15 typedef pair<int,int> pll; 16 const int INF = 0x3f3f3f3f; 17 const int maxn = 200 + 5; 18 19 int n; 20 int t[maxn]; 21 int d[maxn]; 22 23 int dp[maxn][maxn][2]; 24 int path[maxn][maxn][2]; 25 26 int main() 27 { 28 //freopen("in.txt","r",stdin); 29 while(~scanf("%d",&n)) 30 { 31 memset(dp,0,sizeof(dp)); 32 memset(path,-1,sizeof(path)); 33 34 for(int i=1;i<=n;i++) scanf("%d",&t[i]); 35 for(int i=1;i<=n;i++) 36 { 37 scanf("%d",&d[i]); 38 dp[i][i][0]=dp[i][i][1]=0; 39 } 40 41 for(int r=2;r<=n;r++) 42 { 43 for(int i=1;i+r-1<=n;i++) 44 { 45 int j=i+r-1; 46 dp[i][j][0]=min(dp[i+1][j][0]+d[i+1]-d[i],dp[i+1][j][1]+d[j]-d[i]); 47 path[i][j][0]=(dp[i+1][j][0]+d[i+1]-d[i]>=dp[i+1][j][1]+d[j]-d[i]); 48 if(dp[i][j][0]>=t[i] || dp[i][j][0]>INF) 49 dp[i][j][0]=INF; 50 51 dp[i][j][1]=min(dp[i][j-1][0]+d[j]-d[i],dp[i][j-1][1]+d[j]-d[j-1]); 52 path[i][j][1]=(dp[i][j-1][0]+d[j]-d[i]>=dp[i][j-1][1]+d[j]-d[j-1]); 53 if(dp[i][j][1]>=t[j] || dp[i][j][1]>INF) 54 dp[i][j][1]=INF; 55 } 56 } 57 58 int l=1,r=n; 59 int next_p; 60 if(dp[1][n][0]<INF) 61 { 62 printf("1"); 63 l++; 64 next_p=path[1][n][0]; 65 } 66 else if(dp[1][n][1]<INF) 67 { 68 printf("%d",n); 69 r--; 70 next_p=path[1][n][1]; 71 } 72 else 73 { 74 puts("Mission Impossible"); 75 continue; 76 } 77 78 79 while(l<=r) 80 { 81 if(next_p) 82 { 83 printf(" %d",r); 84 next_p=path[l][r--][1]; 85 } 86 else 87 { 88 printf(" %d",l); 89 next_p=path[l++][r][0]; 90 } 91 } 92 printf(" "); 93 } 94 return 0; 95 }