鏈接：https://vjudge.net/problem/UVA-1025
思考：純暴力搜索復雜度太大，考慮使用動態(tài)規(guī)劃晦墙，首先考慮用一個三維數(shù)組記錄火車信息
int train[i][j][k];
i表示時刻t，j表示某個車站，k表示向左或者向右。
int dp[i][j]
i表示時刻t宾娜，j表示車站，用于記錄各個狀態(tài)最短停留時間
然后考慮從終點開始回推液走，每個時刻有三種狀態(tài)：
1碳默、停留1個單位時間
2、坐開向左的車
3缘眶、坐開向右的車
dp[i][j] = dp[i+1][j]+1;
if(j<n&&train[i][j][0]&&i+time[j]<=T)
dp[i][j] = min(dp[i][j],dp[i+time[j]][j+1]);
if(j>1&&train[i][j][1]&&i+time[j-1]<=T)
dp[i][j] = min(dp[i][j],dp[i+time[j-1]][j-1]);
三個狀態(tài)都運行一次嘱根，從而更新出當前最小的停留時間
每個最小的停留時間疊加并且回推，就可以得到最終的最短停留時間巷懈。
代碼：
#include<iostream>
#include<cstring>
using namespace std;
int INF=0x3f3f3f3f; //最大值
int kase=0;
int main(){
int n,T,m,M1,M2;
int time[51];//各個車站到下一站的時間
int dp[201][51];//第i時刻在j車站的最短停留時間
while(cin>>n&&n!=0){
cin>>T;
int train[500][51][2];//i表示時刻该抒，j表示車站，k表示向左或者向右,用于儲存此刻車的信息
memset(time,0,sizeof(time));
memset(dp,0,sizeof(dp));
memset(train,0,sizeof(train));
for(int i=1;i<n;i++)cin>>time[i];
cin>>M1;
for(int i=0;i<M1;i++){
int a;
cin>>a;
int k=a;
for(int j=1;j<=n;j++){
train[k][j][0] = 1;
k+=time[j]; //走向下一站的時刻點
}
}
cin>>M2;
for(int i=0;i<M2;i++){
int a;
cin>>a;
int k=a;
for(int j=n;j>=1;j--){
train[k][j][1] = 1;
k+=time[j-1];
}
}
for(int i= 1;i<=n-1;i++) dp[T][i] = INF;
dp[T][n] = 0;//終點最小值為0顶燕，并且從終點開始向前搜索凑保。
for(int i=T-1;i>=0;i--)
for(int j=1;j<=n;j++){//掃描每一個時間點的每一輛車的信息冈爹，更新dp的最小值。
dp[i][j] = dp[i+1][j]+1;//停留一個單位時間
if(j<n&&train[i][j][0]&&i+time[j]<=T)
dp[i][j] = min(dp[i][j],dp[i+time[j]][j+1]);
if(j>1&&train[i][j][1]&&i+time[j-1]<=T)
dp[i][j] = min(dp[i][j],dp[i+time[j-1]][j-1]);
}
cout<<"Case Number "<<++kase<<": ";
if(dp[0][1]>=INF) cout<<"impossible\n";
else cout<<dp[0][1]<<"\n";
}
return 0;
}
