题目链接：

 

题意：

地铁是线性的，有n个站，编号（1~n）,M1辆从左至右的车，和M2辆从右至左的车，发车时刻给出，然后是，每两个站之间要跑多长时间。一个间谍要从1车站到n车站，但是他要求等车的时间最短，不然间谍会被抓，有可能到不了，输出impossible.

 

分析：

影响每一步的决策只有两个因素，1，时刻，2，哪一个车站。那么DP状态就出来了DP[T][n]在T时刻，第n个站还要等多少分钟。

状态转移：只有三个情况，要么是等一分钟，要么是上左边的车，要么是上右边的车。

 

边界条件dp[T][n] = 0;不用等了。

dp[i][j] = min(dp[i+1][j]+1,dp[i+t[j]][j+1],dp[i+t[j-1]][j-1]);

 

然后就是求has_train[][][2]数组了。具体看程序。

 

#include 
      
       using namespace std;#define INF 0x3f3f3f3fint n;int T;int t[55];int has_train[205][55][2];int dp[205][55];int main(){    int cases = 1;    while(scanf("%d",&n),n)    {        scanf("%d",&T);        for(int i=1; i<=n-1; i++)        {            scanf("%d",&t[i]);        }        int m1,m2;        scanf("%d",&m1);        memset(has_train,0,sizeof(has_train));        while(m1--)        {            int d;            scanf("%d",&d);            for(int j=1; j<=n-1; j++)            {                if(d<=T) has_train[d][j][0] = 1;                d+=t[j];            }        }        scanf("%d",&m2);        while(m2--) {            int d;            scanf("%d",&d);            for(int j=n-1;j>=1;j--) {                if(d<=T) has_train[d][j+1][1] = 1;                d+=t[j];            }        }        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
       
        <=T)                {                    dp[i][j] = min(dp[i][j],dp[i+t[j]][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: ",cases++);        if(dp[0][1]>=INF) printf("impossible\n");        else printf("%d\n",dp[0][1]);    }    return 0;}