模板网站的缺点,长沙网站创建,安仁网络推广软件定制开发,国外网站国内做二维码UVA1025 城市里的间谍 A Spy in the Metro
题面翻译
题目大意
某城市地铁是一条直线#xff0c;有 n n n#xff08; 2 ≤ n ≤ 50 2\leq n\leq 50 2≤n≤50#xff09;个车站#xff0c;从左到右编号 1 … n 1\ldots n 1…n。有 M 1 M_1 M1 辆列车从第 1 1 1 站开…UVA1025 城市里的间谍 A Spy in the Metro
题面翻译
题目大意
某城市地铁是一条直线有 n n n 2 ≤ n ≤ 50 2\leq n\leq 50 2≤n≤50个车站从左到右编号 1 … n 1\ldots n 1…n。有 M 1 M_1 M1 辆列车从第 1 1 1 站开始往右开还有 M 2 M_2 M2 辆列车从第 n n n 站开始往左开。列车在相邻站台间所需的运行时间是固定的因为所有列车的运行速度是相同的。在时刻 0 0 0Mario 从第 1 1 1 站出发目的在时刻 T T T 0 ≤ T ≤ 200 0\leq T\leq 200 0≤T≤200会见车站 n n n 的一个间谍。在车站等车时容易被抓所以她决定尽量躲在开动的火车上让在车站等待的时间尽量短。列车靠站停车时间忽略不计且 Mario 身手敏捷即使两辆方向不同的列车在同一时间靠站Mario 也能完成换乘。
输入格式
输入文件包含多组数据。
每一组数据包含以下 7 7 7 行
第一行是一个正整数 n n n表示有 n n n 个车站。
第二行是为 T T T表示 Mario 在时刻 T T T 会见车站 n n n 的间谍。
第三行有 n − 1 n-1 n−1 个整数 t 1 , t 2 , … , t n − 1 t_1,t_2,\ldots,t_{n-1} t1,t2,…,tn−1其中 t i t_i ti 表示地铁从车站 i i i 到 i 1 i1 i1 的行驶时间。
第四行为 M 1 M_1 M1及从第一站出发向右开的列车数目。
第五行包含 M 1 M_1 M1 个正整数 a 1 , a 2 , … , a M 1 a_1,a_2,\ldots,a_{M_1} a1,a2,…,aM1即每个列车出发的时间。
第六行为 M 2 M_2 M2 即从第 n n n 站出发向左开的列车数目。
第七行包含 M 2 M_2 M2 个正整数 b 1 , b 2 , … , b M 2 b_1,b_2,\ldots,b_{M_2} b1,b2,…,bM2即每个列车出发的时间。
输入文件以一行 0 0 0 结尾。
输出格式
有若干行每行先输出 Case Number XXX : XXX为情况编号从 1 1 1 开始再输出最少等待时间或 impossible无解。
题目描述
PDF
输入格式
输出格式
样例 #1
样例输入 #1
4
55
5 10 15
4
0 5 10 20
4
0 5 10 15
4
18
1 2 3
5
0 3 6 10 12
6
0 3 5 7 12 15
2
30
20
1
20
7
1 3 5 7 11 13 17
0样例输出 #1
Case Number 1: 5
Case Number 2: 0
Case Number 3: impossibleSolution
采用动态规划算法
设dp[i][j]代表第i时刻到在第j站的等待的时间因为要在T时间内达到第n站且要求尽可能多的时间在地铁上度过由此可以知要求dp[T][n]0通过逆向递推建立状态转移方程可以得到以下三种情况
dp[i][j]dp[i1][j]1即dp[i][j] 为在i1时刻在第j站的所等待的时间1dp[i][j]min(dp[it[j]][j1],dp[i][j])即若第i时刻存在向右开的车且此时到达下一个站的时间不大于T时dp[i][j]为第it[j]时刻在第j1站台所等待的时间与在在这个站台等待的时间点最小值dp[i][j]min(dp[it[j-1]][j-1],dp[i][j])即若第i时刻存在向左开的车且此时到达下一个站的时间不大于T时dp[i][j]为第it[j-1]时刻在第j-1站台所等待的时间与在在这个站台等待的时间点最小值
然后最终等待时间为dp[0][1]即在0时刻在1站台时等待的时间
//
// Created by Gowi on 2023/11/23.
//#include iostream
#include cstring#define maxN 100
#define MaxT 300
#define INF 1000000000using namespace std;int T, t[maxN], a[maxN], b[maxN], M1, M2, n;
int has_train[MaxT][maxN][2];// has_train[i][j][1/2] i时刻在第j个站是否有向右(0)/左(1)开的火车
int dp[MaxT][maxN]; //dp[i][j]i时刻在第j个站需要等待多长时间bool init() {int d;cin n;if (n 0) {return false;}memset(t, 0, sizeof(t));memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));memset(has_train, 0, sizeof(has_train));memset(dp, 0, sizeof(dp));cin T;for (int i 1; i n; i) {cin t[i];}cin M1;for (int i 1; i M1; i) {cin a[i];d a[i];for (int j 1; j n; j) {has_train[d][j][0] 1;d t[j];}}cin M2;for (int i 1; i M2; i) {cin b[i];d b[i];for (int j n - 1; j 0; j--) {has_train[d][j1][1] 1;d t[j];}}return true;
}int main() {int k 0;while (init()) {for (int i 1; i n; i) {dp[T][i] INF;}dp[T][n] 0;for (int i T - 1; i 0; i--) {for (int j 1; j n; j) {dp[i][j] dp[i 1][j] 1; // 等待一分钟if (j n has_train[i][j][0] i t[j] T) { //若此时向右有车且到达下一个站的时间不大于Tdp[i][j] min(dp[i][j], dp[i t[j]][j 1]); //状态转移方程}if (j 1 has_train[i][j][1] i t[j-1] T) { //若此时向左有车且到达下一个站的时间不大于Tdp[i][j] min(dp[i][j], dp[i t[j - 1]][j - 1]); //状态转移方程}}}cout Case Number k : ;if (dp[0][1] INF) {cout impossible endl;} else {cout dp[0][1] endl;}}return 0;
}
