DAG的动态规划 (UVA 1025 A Spy in the Metro)

第一遍，刘汝佳提示+题解；回头再看！！！

POINT：

　　dp[time][sta];　　在time时刻在车站sta还需要最少等待多长时间；

　　终点的状态很确定必然是的 dp[T][N] = 0 ---即在T时刻的时候正好达到N站点

　　我们可以从终点的状态往起始的状态转化，一步步走就可以了。

　　has_train[t][i][0];　　t时刻在i车站是否有往右开的火车

　　has_train[t][i][1];　　t时刻在i车站是否有往左开的火车

  1 #include <iostream>
  2 #include <sstream>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <cmath>
  6 #include <string>
  7 #include <vector>
  8 #include <set>
  9 #include <cctype>
 10 #include <algorithm>
 11 #include <cmath>
 12 #include <deque>
 13 #include <queue>
 14 #include <map>
 15 #include <stack>
 16 #include <list>
 17 #include <iomanip>
 18 using namespace std;
 19 
 20 #define INF 0xffffff7
 21 #define maxn 200+10
 22 
 23 int N, T;
 24 int t[maxn];
 25 int dp[maxn][maxn];//dp[i][j] i时刻在j车站最少等候时间
 26 int has_train[maxn][maxn][2];
 27 int main()
 28 {
 29     //freopen("out.txt", "r", stdout);
 30     int kase = 0;
 31     int N;
 32     while(scanf("%d", &N) && N)
 33     {
 34         memset(has_train, 0, sizeof(has_train));
 35         memset(t, 0, sizeof(t));
 36         kase++;
 37         scanf("%d", &T);
 38         for(int i = 1; i < N; i++)
 39             scanf("%d", &t[i]);
 40 
 41         int M1, M2;
 42         scanf("%d", &M1);
 43         for(int i = 1; i <= M1; i++)
 44         {
 45             int start;
 46             scanf("%d", &start);
 47             has_train[start][1][0] = 1;　　// 标记初始站台
 48             for(int j = 1; j < N; j++)
 49             {
 50                 int time = start + t[j];
 51                 if(time <= T)
 52                 {
 53                     has_train[time][j+1][0] = 1;
 54                     start += t[j];
 55                 }
 56             }
 57         }
 58         scanf("%d", &M2);
 59         for(int i = 1; i <= M2; i++)
 60         {
 61             int start;
 62             scanf("%d", &start);
 63             has_train[start][N][1] = 1;　　// 标记初始站台
 64             for(int j = N-1; j >= 1; j--)
 65             {
 66                 int time = start + t[j];
 67                 if(time <= T)
 68                 {
 69                     has_train[time][j][1] = 1;
 70                     //cout << "has[" << time << "][" << j << "][1]  " << endl;
 71                     start += t[j];
 72                 }
 73             }
 74         }
 75         printf("Case Number %d: ", kase);
 76 
 77         for(int i = 1; i < N; i++)
 78             dp[T][i] = INF;
 79         dp[T][N] = 0;
 80         for(int i = T-1; i >= 0; i--)
 81         {
 82             for(int j = 1; j <= N; j++)
 83             {
 84                 dp[i][j] = dp[i+1][j] + 1;  //第T-1时刻在j车站最少等候时间 = 第T时刻在j车站最少等候时间+1; 即决策一---等一分钟
 85                 if(j < N && has_train[i][j][0] && i + t[j] <= T) //决策二
 86                 {
 87                     dp[i][j] = min(dp[i][j], dp[i + t[j]][j+1]);
 88                 }
 89                 if(j > 1 && has_train[i][j][1] && i + t[j-1] <= T) //决策三
 90                 {
 91                     dp[i][j] = min(dp[i][j], dp[i + t[j-1]][j-1]);
 92                 }
 93             }
 94         }
 95 
 96         if(dp[0][1] >= INF) printf("impossible
");
 97         else  printf("%d
", dp[0][1]);
 98     }
 99     return 0;
100 }

View Code