首页 > 代码库 > UVa 1025 城市里的间谍
UVa 1025 城市里的间谍
https://vjudge.net/problem/UVA-1025
题意：一个间谍要从第一个车站到第n个车站去会见另一个，在是期间有n个车站，有来回的车站，让你在时间T内时到达n，并且等车时间最短，输出最短等车时间。
思路：先用一个has_train[t][i][0]来表示在t时刻，在车站i，是否有往右开的车。同理，has_train[t][i][1]用来保存是否有往左开的车。
用d(i,j)表示时刻i，你在车站j，最少还需要等待多长时间。边界条件是d(T,n)=0，其他d(T,i)为正无穷。
每次有三种决策:
①：等一分钟。
②：搭成往右开的车（如果有）。
③：搭成往左开的车（如果有）。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const int INF = 0x3f3f3f3f; 7 8 int T, n, dp[205][60], m1, m2, has_train[255][55][2],t[80]; 9 10 int main()11 {12 //freopen("D:\\txt.txt", "r", stdin);13 int kase = 0;14 while (cin >> n && n)15 {16 cin >> T; 17 for (int i = 1; i < n; i++)18 {19 cin >> t[i];20 }21 memset(has_train, 0, sizeof(has_train));22 int x;23 cin >> m1;24 for (int i = 0; i < m1; i++)25 {26 cin >> x;27 for (int j = 1; x<=T && j <= n; j++)28 {29 has_train[x][j][0] = 1;30 x += t[j];31 }32 }33 34 cin >> m2;35 for (int i = 0; i < m2; i++)36 {37 cin >> x;38 for (int j = n; x <=T && j >1; j--)39 {40 has_train[x][j][1] = 1;41 x += t[j-1];42 }43 }44 45 46 for (int i = 1; i <= n - 1; i++) dp[T][i] = INF;47 dp[T][n] = 0;48 for (int i = T - 1; i >= 0; i--)49 {50 for (int j = 1; j <= n; j++)51 {52 dp[i][j] = dp[i + 1][j] + 1; //等待一个单位53 if (j < n && has_train[i][j][0] && i + t[j] <= T)54 dp[i][j] = min(dp[i][j], dp[i + t[j]][j + 1]); //往右55 if (j>1 && has_train[i][j][1] && i + t[j - 1] <= T)56 dp[i][j] = min(dp[i][j], dp[i + t[j - 1]][j - 1]); //往左57 }58 }59 cout << "Case Number " << ++kase << ": ";60 if (dp[0][1] >= INF) cout << "impossible" << endl;61 else cout << dp[0][1] << endl;62 }63 return 0;64 }
UVa 1025 城市里的间谍
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。