A Spy in the Metro UVA - 1025

题意：

有一个间谍，要去n城。n个城市之间有铁路连接。

1. 第 i i i个城市和第 i + 1 i+1 i+1个城市之间的时间是 t i t_{i} ti​
2. 有双向的火车，从左出发的有 m 1 m_1 m1​个，从右出发的有 m 2 m_2 m2​个。
3. 每个火车都有出发时间。

现给你一个时间T，间谍要在T时间上在n城与人接应。现在要求缩小候车时间。

思路:

1. 时间是单向流逝的，是一个天然的“序”，影响到决策的只有当前时间和所处的车站，所以可以用dp（i，j）表示时刻i，你在车站j（编号为1~n）,最少还需要等待多长时间。边界条件是d（T，n） = 0；其他d（T，i）（i不等于n）为正无穷。
2. 有如下三个决策。
   决策1：等一分钟。
   决策2：搭乘往右开的车（如果有）
   决策3：搭乘往左开的车（如果有）

AC

#include <iostream>
#include <bits/stdc++.h>
#define For(i,x,y) for(int i=(x); i<=(y); i++)
#define fori(i,x,y) for(int i=(x); i<(y); i++)
#define rep(i,y,x) for(int i=(y); i>=(x); i--)
#define mst(x,a) memset(x,a,sizeof(x))
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int>pa;
typedef pair<ll,ll>pai;
const int INF = 0x3f3f3f3f;
int dp[250][60];
bool train[250][60][2];
int n, t[60];
int main()
{
  //  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int kase = 0;
    while(scanf("%d", &n)&&n){
        int T; scanf("%d", &T);
        fori(i,1,n)scanf("%d", &t[i]);
        int m, x, k;
        mst(dp,0); mst(train,0);
        ///right
        scanf("%d", &m);
        fori(j,0,m){
            scanf("%d", &x);
            int cnt = 1;
            for(k=x; k<=T && cnt<n ; k+=t[cnt], cnt++)train[k][cnt][0] = 1;
            train[k][cnt][0] = 1;
        }
        ///left
        scanf("%d", &m);
        fori(j,0,m){
            scanf("%d", &x);
            int cnt = n;
            for(k=x; k<=T && cnt>1 ; k+=t[cnt-1], cnt--)train[k][cnt][1] = 1;
            train[k][cnt][1] = 1;
        }
        ///dp
        For(i,1,n)dp[T][i] = INF;
        dp[T][n] = 0;
        rep(i,T-1,0){
            For(j,1,n){
                dp[i][j] = dp[i+1][j] + 1;
                if(j<n && i+t[j]<=T && train[i][j][0])dp[i][j] = min(dp[i][j], dp[i+t[j]][j+1]);
                if(j>1 && i+t[j-1]<=T && train[i][j][1])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;
}