题意：

某城市地铁是线性得，有n个车站，从左到右编号为1至n。有M1辆列车从第1站开始往右开，有M2辆列车从第n站开始往左开。在时刻0，Mario从第1站出发，目的是在时刻T会见车站n得一个间谍。在车站等车时容易被抓，所以她决定尽量躲在开动的火车上，让在车站等待的总时间尽量短。列车靠站停车时间忽略不计，并且Mario身手敏捷，即使两辆方向不同的列车在同一时间靠站，Mario也能完成换乘。

 

分析：

状态：d[i][j]代表时刻i，在车站j，最少的等待时间。边界情况d[T][n]=0，其余的d[T][i]为无穷大，i<T.

       有以下3种决策：

1，原地等待1分钟

2，搭乘往右开的车（如果有）

3，搭乘往左开的车（如果有）

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int INF=1e9;int t[25];int dp[205][55];bool has_train[205][55][2];int main(){    //freopen("in.txt","r",stdin);    int n,T;    int kase=0;    while(cin>>n,n)    {        memset(has_train,0,sizeof(has_train));        scanf("%d",&T);        for(int i=1; i
         
          T) break;                has_train[d][j][0]=1;            }        }        scanf("%d",&M);        for(int i=0; i
          
           =1; j--) { d+=t[j]; if(d>T) break; has_train[d][j][1]=1; } } for(int i=1; i<=n-1; i++) dp[T][i]=INF; dp[T][n]=0; for(int i=T-1; i>=0; i--) for(int j=1; j<=n; j++) { dp[i][j]=dp[i+1][j]+1; if(j
           
            1 && has_train[i][j][1] && i+t[j-1]<=T) dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]); } printf("Case Number %d: ",++kase); if(dp[0][1]>=INF) printf("impossible\n"); else printf("%d\n",dp[0][1]); } return 0;}