题目链接：http://fastvj.rainng.com/contest/306591#problem/A
题目大意：
某城市的地铁是线性的，有n（2≤n≤50）个车站，从左到右编号为1～n。有M1辆列车从 第1站开始往右开，还有M2辆列车从第n站开始往左开。在时刻0，Mario从第1站出发，目的 是在时刻T（0≤T≤200）会见车站n的一个间谍。在车站等车时容易被抓，所以她决定尽量躲 在开动的火车上，让在车站等待的总时间尽量短。列车靠站停车时间忽略不计，且Mario身 手敏捷，即使两辆方向不同的列车在同一时间靠站，Mario也能完成换乘。

输入第1行为n，第2行为T，第3行有n－1个整数t1, t2,…, tn－1（1≤ti≤70），其中ti表示地 铁从车站i到i＋1的行驶时间（两个方向一样）。第4行为M1（1≤M1≤50），即从第1站出发 向右开的列车数目。第5行包含M1个整数d1, d2,…, dM1（0≤di≤250，di＜di＋1），即各列车的 出发时间。第6、7行描述从第n站出发向左开的列车，格式同第4、5行。输出仅包含一行， 即最少等待时间。无解输出impossible。

思路：

题解：时间是单向流逝的，是一个天然的“序”。影响到决策的只有当前时间和所处的车站，
所以可以用d(i,j)表示时刻i，你在车站j（编号为1～n），最少还需要等待多长时间。

边界条件 是d(T,n)=0，其他d(T,i)（i不等于n）为正无穷。有如下3种决策。

决策1：等1分钟。
决策2：搭乘往右开的车（如果有）。
决策3：搭乘往左开的车（如果有）。

我的思路：

题解是从时间T推到1.相对难理解。所以我从1推到T。
边界条件 是d(0,1)=0，其他d(T,i)（i不等于n）为正无穷。有如下3种决策。

决策1：等1分钟。
决策2：搭乘往右开的车（如果有）。
决策3：搭乘往左开的车（如果有）。

上面的代码中有一个vis数组，其中vis[t][i][0]表示时刻t，在车站i是否有往右开的火车，
vis[t][i][1]类似，不过记录的是往左开的火车。输入预处理一下。

代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int t[1000];
int c[1000];
int d[1000];
int vis[2005][55][2];
int dp[2005][55];
int main()
{
    int n, T, m1, m2, CUT=1;
    while(scanf("%d",&n),n)
    {
        memset(vis, 0, sizeof(vis));
        scanf("%d",&T);
        for(int i=1;i<n;i++)
        {
            scanf("%d",&t[i]);
        }
        scanf("%d",&m1);
        for(int i=1;i<=m1;i++)
        {
            scanf("%d",&c[i]);
            int g=c[i];
            for(int j=1;j<=n;j++)
            {
                vis[g][j][0]=1;
                g+=t[j];
            }
        }
        scanf("%d",&m2);
        for(int i=1;i<=m2;i++)
        {
            scanf("%d",&d[i]);
            int g=d[i];
            for(int j=n;j>=1;j--)
            {
                vis[g][j][1]=1;
                g+=t[j-1];
            }
        }

        for(int p=0;p<=T;p++)
        {
            for(int i=1;i<=n;i++)
            {
                dp[p][i]=(1<<31)-1;
            }
        }
        dp[0][1]=0;
        for(int i=0;i<T;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(dp[i][j]!=(1<<31)-1)
                {
                    dp[i+1][j]=min(dp[i][j]+1, dp[i+1][j]);//等待

                    if(j<n&&i+t[j+1]<=T&&vis[i][j][0])//往右开
                    {
                        dp[i+t[j]][j+1]=min(dp[i][j], dp[i+t[j]][j+1]);
                    }
                    if(j>1&&i+t[j-1]<=T&&vis[i][j][1])//往左开
                    {
                        dp[i+t[j-1]][j-1]=min(dp[i][j], dp[i+t[j-1]][j-1]);
                    }
                }
            }
        }
        if(dp[T][n]==(1<<31)-1)
        {
            printf("Case Number %d: impossible\n",CUT++);
        }
        else
        {
            printf("Case Number %d: %d\n",CUT++,dp[T][n]);
        }
    }

    return 0;
}