http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=35913
预处理出每个时间、每个车站是否有火车
为了方便判断是否可行，倒推处理，每次有三种决策：原地坐等一分钟、搭车向左（如果有车）、搭车向右（如果有车）
1 /**/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 using namespace std; 8 const int mxn=300; 9 int n,T; 10 bool h[mxn][mxn][2]; 11 int ti[mxn]; 12 int m,d,e; 13 int f[mxn][mxn]; 14 void clear(){ 15 memset(ti,0,sizeof(ti)); 16 memset(h,0,sizeof(h)); 17 memset(f,111,sizeof(f)); 18 } 19 int main(){ 20 int cnt=0; 21 while(scanf("%d",&n) && n){ 22 clear(); 23 scanf("%d",&T); 24 int i,j; 25 for(i=1;i<n;i++)scanf("%d",&ti[i]);//车站距离 26 scanf("%d",&m); 27 for(i=1;i<=m;i++) 28 { 29 scanf("%d",&d);//左边发车时间 30 for(j=1;d<=T && j<=n;d+=ti[j],j++){ 31 h[d][j][0]=1; 32 } 33 } 34 scanf("%d",&m); 35 for(i=1;i<=m;i++) 36 { 37 scanf("%d",&e);//右边发车时间 38 for(j=n;e<=T && j>=1;j--,e+=ti[j]){ 39 h[e][j][1]=1; 40 } 41 } 42 //以上全是初始化 43 f[T][n]=0; 44 for(i=T-1;i>=0;i--){//倒推 45 for(j=1;j<=n;j++){ 46 f[i][j]=f[i+1][j]+1;//等待 47 if(j<n && h[i][j][0] && i+ti[j]<=T) 48 f[i][j]=min(f[i][j],f[i+ti[j]][j+1]);//向右 49 if(j>1 && h[i][j][1] && i+ti[j-1]<=T) 50 f[i][j]=min(f[i][j],f[i+ti[j-1]][j-1]);//向左 51 } 52 } 53 printf("Case Number %d: ",++cnt); 54 if(f[0][1]>=0xff) printf("impossible "); 55 else printf("%d ",f[0][1]); 56 } 57 return 0; 58 }