转自：http://www.cnblogs.com/20143605--pcx/p/5200518.html
注意什么是状态，因为每次都要知道所处的位置，所以有0， 1 来表示在左边还是右边，， 对于判断会不会时间超限，就用本身的子结构（自然表示的时间）来判断。。
还有这个地方就像是背包一样可以用滚动数组优化，因为这个地方也是只由上一个状态决定，，所以用 ^ 自然表示 奇偶性。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<string> #include<cstring> #include<iomanip> #include<iostream> #include<stack> #include<cmath> #include<map> #include<vector> #define ll long long #define inf 0x3f3f3f3f #define INF 1000000000 #define bug1 cout<<"bug1"<<endl; #define bug2 cout<<"bug2"<<endl; #define bug3 cout<<"bug3"<<endl; using namespace std; const int maxn=10005; int dp[2][maxn][2]; int x[maxn],t[maxn]; int main() { int n; while(~scanf("%d",&n)) { for(int i=0;i<n;++i){ scanf("%d%d",x+i,t+i); dp[1][i][0]=dp[1][i][1]=dp[0][i][0]=dp[0][i][1]=(t[i]>0)?0:INF; } for(int i=n-2;i>=0;--i){ for(int j=i+1;j<n;++j){ dp[i&1][j][0]=dp[i&1][j][1]=inf; if(dp[(i&1)^1][j][0]!=inf&&dp[(i&1)^1][j][0]+x[i+1]-x[i]<t[i]) dp[i&1][j][0]=min(dp[i&1][j][0],dp[(i&1)^1][j][0]+x[i+1]-x[i]); if(dp[(i&1)^1][j][1]!=inf&&dp[(i&1)^1][j][1]+x[j]-x[i]<t[i]) dp[i&1][j][0]=min(dp[i&1][j][0],dp[(i&1)^1][j][1]+x[j]-x[i]); if(dp[i&1][j-1][0]!=inf&&dp[i&1][j-1][0]+x[j]-x[i]<t[j]) dp[i&1][j][1]=min(dp[i&1][j][1],dp[i&1][j-1][0]+x[j]-x[i]); if(dp[i&1][j-1][1]!=inf&&dp[i&1][j-1][1]+x[j]-x[j-1]<t[j]) dp[i&1][j][1]=min(dp[i&1][j][1],dp[i&1][j-1][1]+x[j]-x[j-1]); } } if(dp[0][n-1][1]==inf&&dp[0][n-1][0]==inf) printf("No solution\n"); else printf("%d\n",min(dp[0][n-1][0],dp[0][n-1][1])); } return 0; }
