UVa 1025 (动态规划) A Spy in the Metro

题意：

有线性的n个车站，从左到右编号分别为1~n。有M1辆车从第一站开始向右开，有M2辆车从第二站开始向左开。在0时刻主人公从第1站出发，要在T时刻回见车站n 的一个间谍(忽略主人公的换乘时间)。输出最少的等待时间，如果无解输出impossible。

分析：

d(i, j)表示第i时刻在第j个车站，最少还需要的等待时间。边界是：d(T, n) = 0, d(T, i) = +∞

预处理：

has_train[t][i][0]数组是用来记录t时刻第i个车站是否有向右开的车，类似has_train[t][i][1]记录的是向左开的车。

有3种决策：

1. 等一分钟
2. 搭乘向左开的车(如果有的话)
3. 搭乘向右开的车(如果有的话)

边界没有处理到位，WA了好多次。

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int INF = ;

 int has_train[][][], t[], dp[][];

 int main(void)

 {

     #ifdef LOCAL

         freopen("1025in.txt", "r", stdin);

     #endif

     int kase = , n, T;

     while(scanf("%d", &n) ==  && n)

     {

         scanf("%d", &T);

         for(int i = ; i < n; ++i)    dp[T][i] = INF;

         dp[T][n] = ;

         memset(has_train, , sizeof(has_train));

         for(int i = ; i < n; ++i)    scanf("%d", &t[i]);

         int m, ti;

         scanf("%d", &m);

         while(m--)

         {

             scanf("%d", &ti);

             for(int i = ; i < n; ++i)

             {

                 if(ti <= T)    has_train[ti][i][] = ;

                 ti += t[i];

             }

         }

         scanf("%d", &m);

         while(m--)

         {

             scanf("%d", &ti);

             for(int j = n-; j >= ; --j)

             {

                 if(ti <= T)    has_train[ti][j + ][] = ;

                 ti += t[j];

             }

         }

         for(int i = T - ; i >= ; --i)

         {

             for(int j = ; j <= n; ++j)

             {

                 dp[i][j] = dp[i+][j] + ;

                 if(j < n && has_train[i][j][] && i + t[j] <= T)

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

                 if(j >  && has_train[i][j][] && i + t[j-] <= T)

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

             }

         }

         printf("Case Number %d: ", ++kase);

         if(dp[][] >= INF)    puts("impossible");

         else    printf("%d\n", dp[][]);

     }

     return ;

 }

代码君