UVA 1025 "A Spy in the Metro " (DAG上的动态规划?? or 背包问题??)

传送门

 

参考资料:

  [1]:算法竞赛入门经典:第九章 DAG上的动态规划

题意:

  Algorithm城市的地铁有 n 个站台,编号为 1~n,共有 M1+M2 辆列车驶过;

  其中 M1 辆列车从 1 号站台驶向 n 号站台,M2 辆列车从 n 号站台驶向 1 号地铁;

  (单程线,M1 辆列车到达 n 号站台后不会回返,同理 M2)

  特工 Maria 要在 T 时刻到达 n 号站台与特务会面,但为了保证安全,在会面前尽量呆在行进的列车中;

  现给出你这 M1+M2 辆列车的发车时刻;

  问如何换乘列车使得特工 Maria 能在 T 时刻前到达 n 号站台,并且在换乘期间在站台的停留时间最短;

  如果可以在规定时间到达 n 站台,输出在站台停留的最短时间,反之,输出 "impossible";

题解:

  看完书上的解释后,感觉,不像是DAG上的动态规划,倒有点像背包的味道;

 1 int n,t;
 2 int m1,m2;
 3 int f[maxn];///前m1辆列车的发车时刻
 4 int e[maxn];///后m2辆列车的发车时刻
 5 int c[maxn];///c[i]:车站i到车站i+1的时间花费
 6 /**
 7     (i,j):i时刻在车站j
 8     dp[i][j]:从(i,j)->(t,n)所需等待的最少时间
 9 */
10 int dp[maxn][60];
11 /**
12     hasTrain[i][j][0]=true:i时刻在车站j有到j+1的火车
13     hasTrain[i][j][1]=true:i时刻在车站j有到j-1的火车
14 */
15 bool hasTrain[maxn][60][2];

  最关键的便是dp[ i ][ j ]的定义;

  之所以定义成二维的,是因为决策受当前时间和所处车站的影响,有两个影响因素;

  定义好后,便是找状态转移方程了;

  首先预处理出 hasTrain 数组:

UVA 1025 "A Spy in the Metro " (DAG上的动态规划?? or 背包问题??)
 1 void Init()///预处理hasTrain
 2 {
 3     mem(hasTrain,false);
 4     for(int i=1;i <= m1;++i)
 5     {
 6         int cnt=f[i];
 7         hasTrain[cnt][1][0]=true;
 8         for(int j=2;j <= n;++j)
 9         {
10             cnt += c[j-1];
11             hasTrain[cnt][j][0]=true;
12         }
13     }
14     for(int i=1;i <= m2;++i)
15     {
16         int cnt=e[i];
17         hasTrain[cnt][n][1]=true;
18         for(int j=n-1;j >= 1;--j)
19         {
20             cnt += c[j];
21             hasTrain[cnt][j][1]=true;
22         }
23     }
24 }
预处理hasTrain[]

  令dp[t][n]=0,dp[t][1,2,...,n-1]=INF;

  按照时间逆序遍历,对于状态 dp[ i ][ j ]:

  ①等一分钟,下一分钟从车站 j 出发到达(t , n);

  ②搭乘往右开的列车;

  ③搭乘往左开的列车;

  UVA 1025 "A Spy in the Metro " (DAG上的动态规划?? or 背包问题??)

AC代码:

UVA 1025 "A Spy in the Metro " (DAG上的动态规划?? or 背包问题??)
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define INF 0x3f3f3f3f
 4 #define mem(a,b) memset(a,b,sizeof(a))
 5 const int maxn=200+50;
 6 
 7 int n,t;
 8 int m1,m2;
 9 int f[maxn];///前m1辆列车的发车时刻
10 int e[maxn];///后m2辆列车的发车时刻
11 int c[maxn];///c[i]:车站i到车站i+1的时间花费
12 /**
13     (i,j):i时刻在车站j
14     dp[i][j]:从(i,j)->(t,n)所需等待的最少时间
15 */
16 int dp[maxn][60];
17 /**
18     hasTrain[i][j][0]=true:i时刻在车站j有到j+1的火车
19     hasTrain[i][j][1]=true:i时刻在车站j有到j-1的火车
20 */
21 bool hasTrain[maxn][60][2];
22 
23 void Init()///预处理hasTrain
24 {
25     mem(hasTrain,false);
26     for(int i=1;i <= m1;++i)
27     {
28         int cnt=f[i];
29         hasTrain[cnt][1][0]=true;
30         for(int j=2;j <= n;++j)
31         {
32             cnt += c[j-1];
33             hasTrain[cnt][j][0]=true;
34         }
35     }
36     for(int i=1;i <= m2;++i)
37     {
38         int cnt=e[i];
39         hasTrain[cnt][n][1]=true;
40         for(int j=n-1;j >= 1;--j)
41         {
42             cnt += c[j];
43             hasTrain[cnt][j][1]=true;
44         }
45     }
46 }
47 void Solve()
48 {
49     Init();
50     for(int i=1;i < n;++i)
51         dp[t][i]=INF;
52     dp[t][n]=0;
53     for(int i=t-1;i >= 0;--i)
54     {
55         for(int j=1;j <= n;++j)
56         {
57             dp[i][j]=dp[i+1][j]+1;
58             if(j < n && hasTrain[i][j][0] && i+c[j] <= t)
59                 dp[i][j]=min(dp[i][j],dp[i+c[j]][j+1]);
60             if(j > 1 && hasTrain[i][j][1] && i+c[j-1] <= t)
61                 dp[i][j]=min(dp[i][j],dp[i+c[j-1]][j-1]);
62         }
63     }
64     if(dp[0][1] >= INF)
65         puts("impossible");
66     else
67         printf("%d\n",dp[0][1]);
68 }
69 int main()
70 {
71     int kase=0;
72     while(~scanf("%d",&n) && n)
73     {
74         scanf("%d",&t);
75         for(int i=1;i < n;++i)
76             scanf("%d",c+i);
77         scanf("%d",&m1);
78         for(int i=1;i <= m1;++i)
79             scanf("%d",f+i);
80         scanf("%d",&m2);
81         for(int i=1;i <= m2;++i)
82             scanf("%d",e+i);
83 
84         printf("Case Number %d: ",++kase);
85         Solve();
86     }
87     return 0;
88 }
View Code

 

上一篇:PAT (Basic Level) Practice (中文)--1025 反转链表


下一篇:#Leetcode# 1025. Divisor Game