这是紫书上的第一个dp哈。
1.状态定义:dp[i][j]---->到时刻i的时候（出发的时候时刻为0，约定时间为时刻time），从j号车站开往N号车站，在车站等待的最少的时间。
2.这个人当前的策略：
α.在车站等待一个单位的时间（该站此时没有发车时应该这么做）
β.坐上开往左边的火车
γ.坐上开往右边的火车
3.状态转移方程:dp[i][j] = min(dp[i+1][j]+1,dp[i+t[j]][j+1],dp[i+t[j-1]][j-1])
我们可以做一个乘车时刻表来记录i时刻j车站是否有车经过。
dp[time][N] = 0,其余初始化为正无穷。
同时，可以看出，时刻i一直在往大的方向转移，所以，i的循环应该是逆序。
还有，按道理来说这个人不一定只在该车站仅仅等待1个单位时间，应该可以等待k个，然而在更新dp[i+1][j]时（由于是逆序循环，所以dp[i+1][j]先被考虑）也考虑了等待的问题，所以只需要考虑当前时刻的这1单位时刻等待与否，之前的k-1个单位时刻其实已经考虑过了。
贴AC代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn1 55
#define maxn2 255
#define F 0x3f
#define INF 0x3f3f3f3f
using namespace std;
int timetable[][maxn2][maxn1];
int t[maxn1],dp[maxn2][maxn1];
int main()
{
int N,cas = ;
while(scanf("%d",&N) == && N){
int time;
scanf("%d",&time);
for(int i = ;i < N;++i) scanf("%d",&t[i]);
memset(timetable,,sizeof(timetable));
memset(dp,F,sizeof(dp));
int M1,M2,train;
scanf("%d",&M1);
for(int i = ;i < M1;++i){
scanf("%d",&train);
int sum = train;
for(int j = ,k = ;j < N && k <= N;sum += t[j],++j,++k){
if(sum > time) break;
timetable[][sum][k] = ;
}
}
scanf("%d",&M2);
for(int i = ;i < M2;++i){
scanf("%d",&train);
int sum = train;
for(int j = N - ,k = N;j >= && k >= ;sum += t[j],--j,--k){
if(sum > time) break;
timetable[][sum][k] = ;
}
}
dp[time][N] = ;
for(int i = time - ;i >= ;--i){
for(int j = ;j <= N;++j){
dp[i][j] = dp[i + ][j] + ;
if(timetable[][i][j] && j < N && i + t[j] <= time)
dp[i][j] = min(dp[i][j],dp[i + t[j]][j + ]);
if(timetable[][i][j] && j > && i + t[j - ] <= time)
dp[i][j] = min(dp[i][j],dp[i + t[j - ]][j - ]);
}
}
if(dp[][] >= INF) printf("Case Number %d: impossible\n",cas++);
else printf("Case Number %d: %d\n",cas++,dp[][]);
}
return ;
}