首页 > 代码库 > UVa 1025 (动态规划) A Spy in the Metro
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种决策：
- 等一分钟
- 搭乘向左开的车(如果有的话)
- 搭乘向右开的车(如果有的话)
边界没有处理到位，WA了好多次。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int INF = 1000000000; 8 int has_train[255][55][2], t[55], dp[255][55]; 9 10 int main(void)11 {12 #ifdef LOCAL13 freopen("1025in.txt", "r", stdin);14 #endif15 16 int kase = 0, n, T;17 while(scanf("%d", &n) == 1 && n)18 {19 scanf("%d", &T);20 for(int i = 1; i < n; ++i) dp[T][i] = INF;21 dp[T][n] = 0;22 memset(has_train, 0, sizeof(has_train));23 24 for(int i = 1; i < n; ++i) scanf("%d", &t[i]);25 int m, ti;26 scanf("%d", &m);27 while(m--)28 {29 scanf("%d", &ti);30 for(int i = 1; i < n; ++i)31 {32 if(ti <= T) has_train[ti][i][0] = 1;33 ti += t[i];34 }35 }36 scanf("%d", &m);37 while(m--)38 {39 scanf("%d", &ti);40 for(int j = n-1; j >= 1; --j)41 {42 if(ti <= T) has_train[ti][j + 1][1] = 1;43 ti += t[j];44 }45 }46 47 for(int i = T - 1; i >= 0; --i)48 {49 for(int j = 1; j <= n; ++j)50 {51 dp[i][j] = dp[i+1][j] + 1;52 if(j < n && has_train[i][j][0] && i + t[j] <= T)53 dp[i][j] = min(dp[i][j], dp[i + t[j]][j+1]);54 if(j > 1 && has_train[i][j][1] && i + t[j-1] <= T)55 dp[i][j] = min(dp[i][j], dp[i + t[j-1]][j-1]);56 }57 }58 59 printf("Case Number %d: ", ++kase);60 if(dp[0][1] >= INF) puts("impossible");61 else printf("%d\n", dp[0][1]);62 }63 64 return 0;65 }
UVa 1025 (动态规划) A Spy in the Metro
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。