區間dp-zoj3541-The Last Puzzle

題目大意：   在數軸上，有n個按鈕，位置遞增為d1,d2,..dn，每個按鈕對應一個時間為t1,t2,...tn.每次每個按鈕按下後，t1秒後會自動彈起來。每走單位距離花費單位時間，問以怎樣的順序按，能夠保證所有 的按鈕都能夠被按下去。   解題思路：   區間dp.   這題hdu 4053提交過不了，spj可能有問題。   對於某一區間A~B的按鈕，一定是先按某個端點，如果不是,假設先按中間的K，然後肯定要按一個端點，再之後會按另外一個端點，中間肯定會經過K點，所以先按k不如後按k。   dp[i][j][0]表示在區間i~j內先按左邊端點能達到的最小的時間，dp[i][j][1]表示先按右端點能達到的最小時間。   dp[i][j][0]=Min(dp[i+1][j][0]+dp[i+1]-dp[i],dp[i+1][j]+dp[j][-dp[i]);   path[i][j][]表示對應狀態表示的端點（左還是右）。   代碼：

 
#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<set>  
#include<stack>  
#include<list>  
#include<queue>  
#define eps 1e-6  
#define INF 0x3fffffff  
#define PI acos(-1.0)  
#define ll __int64  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
  
//freopen("data.in","r",stdin);  
//freopen("data.out","w",stdout);  
  
#define Maxn 220  
  
ll dp[Maxn][Maxn][2];  
int pa[Maxn][Maxn][2];  
//dp[i][j][0]表示區間i~j從左邊端點開始按 dp[][][1]表示從右邊端點開始  
//path[i][j][k]表示與之對應的狀態。  
int ti[Maxn],di[Maxn];  
int n;  
  
int main()  
{  
   while(scanf("%d",&n)!=EOF)  
   {  
      for(int i=1;i<=n;i++)  
         scanf("%d",&ti[i]);  
      for(int i=1;i<=n;i++)  
         scanf("%d",&di[i]);  
      memset(dp,0,sizeof(dp)); //時間為0  
      for(int gap=2;gap<=n;gap++)  
      {  
         for(int i=1;i+gap-1<=n;i++)  
         {  
            int j=i+gap-1;  
  
            if(dp[i+1][j][0]+di[i+1]-di[i]<dp[i+1][j][1]+di[j]-di[i])  
            {  
               dp[i][j][0]=dp[i+1][j][0]+di[i+1]-di[i];  
               pa[i][j][0]=0;//表示從左邊過來  
            }  
            else  
            {  
               dp[i][j][0]=dp[i+1][j][1]+di[j]-di[i];  
               pa[i][j][0]=1;//表示從右邊走  
            }  
            if(ti[i]<=dp[i][j][0]||dp[i][j][0]>=INF)  
               dp[i][j][0]=INF;  
  
            if(dp[i][j-1][1]+di[j]-di[j-1]<=dp[i][j-1][0]+di[j]-di[i])  
            {  
               dp[i][j][1]=dp[i][j-1][1]+di[j]-di[j-1];  
               pa[i][j][1]=1; //從右邊  
            }  
            else  
            {  
               dp[i][j][1]=dp[i][j-1][0]+di[j]-di[i];  
               pa[i][j][1]=0;//從左邊  
            }  
            if(ti[j]<=dp[i][j][1]||dp[i][j][1]>=INF)  
               dp[i][j][1]=INF; //置為無效狀態  
         }  
      }  
      int l,r,va;  
      if(dp[1][n][0]<INF) //有效狀態  
      {  
         printf("%d",1);  
         l=2,r=n;  
         va=pa[1][n][0];  
      }  
      else if(dp[1][n][1]<INF)  
      {  
         printf("%d",n);  
         l=1,r=n-1;  
         va=pa[1][n][1];  
      }  
      else  
      {  
         printf("Mission Impossible\n");  
         continue;  
      }  
      while(l<=r)  
      {  
         if(va==0)  
         {  
            printf(" %d",l);  
            va=pa[l][r][0];  
            l++;  
         }  
         else  
         {  
            printf(" %d",r);  
            va=pa[l][r][1];  
            r--;  
         }  
      }  
      putchar('\n');  
   }  
   return 0;  
}