链接：https://vjudge.net/problem/UVA-1025
思考：纯暴力搜索复杂度太大，考虑使用动态规划，首先考虑用一个三维数组记录火车信息
int train[i][j][k];
i表示时刻t，j表示某个车站，k表示向左或者向右。
int dp[i][j]
i表示时刻t，j表示车站，用于记录各个状态最短停留时间
然后考虑从终点开始回推，每个时刻有三种状态：
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]);
三个状态都运行一次，从而更新出当前最小的停留时间
每个最小的停留时间叠加并且回推，就可以得到最终的最短停留时间。
代码：
#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;
}
