首页 > 代码库 > 【luogu2583】地铁间谍

【luogu2583】地铁间谍

2024-10-11 04:10:02   212人阅读

题目描述

特工玛利亚被送到S市执行一个特别危险的任务。她需要利用地铁完成他的任务，S市的地铁只有一条线路运行，所以并不复杂。

玛利亚有一个任务，现在的时间为0，她要从第一个站出发，并在最后一站的间谍碰头。玛利亚知道有一个强大的组织正在追踪她，她知道如果一直呆在一个车站，她会有很大的被抓的风险，躲在运行的列车中是比较安全的。所以，她决定尽可能地呆在运行的列车中，她只能往前或往后坐车。

玛利亚为了能准时且安全的到达最后一个车站与对方碰头，需要知道在在车站最小等待时间总和的计划。你必须写一个程序，得到玛丽亚最短的等待时间。当然，到了终点站之后如果时间还没有到规定的时刻，她可以在车站里等着对方，只不过这个等待的时刻也是要算进去的。

这个城市有n个车站，编号是1-n，火车是这么移动的：从第一个车站开到最后一个车站。或者从最后一站发车然后开会来。火车在每特定两站之间行驶的时间是固定的，我们也可以忽略停车的时间，玛利亚的速度极快，所以他可以迅速上下车即使两辆车同时到站。

输入输出格式

输入格式：

输入文件包含多组数据，每组数据都由7行组成

第1行：一个正整数N（2<=N<=50）表示站的数量

第2行：一个正整数T（0<=T<=200）表示需要的碰头时间

第3行：1-（n-1）个正整数（0<ti<70）表示两站之间列车的通过时间

第4行：一个整数M1（1<=M1<=50）表示离开第一个车站的火车的数量

第5行：M1个正整数：d1，d2……dn，（0<=d<=250且di<di+1）表示每一列火车离开第一站的时间

第6行：一个正整数M2（1<=M2<=50）表示离开第N站的火车的数量

第7行：M2个正整数：e1,e2……eM2,(0<=e<=250且ei<ei+1)表示每一列火车离开第N站的时间

最后一行有一个整数0。

输出格式：

对于每个测试案例，打印一行“Case Number N: ”（N从1开始）和一个整数表示总等待的最短时间或者一个单词“impossible”如果玛丽亚不可能做到。按照样例的输出格式。

输入输出样例

输入样例#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: impossible

说明

第一组样例说明，她0分钟时上车，在3号站下车，立刻坐上（0分始发）15分开的车回去，到2号车站，立刻坐上（20分始发）25开的车到终点，50分到，还需要等待5分钟。

题解

设在时刻i，车站j到结束最短需要等待f(i,j)分钟，得状态转移方程：

f(i,j)=min{
     f(i+1,j)+1
     f(i+t[j-1],j-1) (若时刻i有向左走的车)
     f(i+t[j],j+1) (若时刻i有向右走的车)
}

 

 1 #include <iostream>
 2 #include <cstring>
 3 #define maxt 210
 4 #define maxn 60
 5 #define inf 1000
 6 using namespace std;
 7 bool has_train[maxt][maxn][2];
 8 int dp[maxt][maxn];
 9 int n, tt, t[maxn], m1, m2, d;
10 int main()
11 {
12     int cnt = 1;
13     while (true)
14     {
15         cin >> n;
16         if (n == 0) break;
17         cin >> tt;
18         for (int i = 1; i<n; i++) cin >> t[i];
19 
20         //预处理has_train数组
21         memset(has_train, false, maxt * maxn * 2);
22         cin >> m1;
23         while (m1--)
24         {
25             cin >> d;
26             for (int j = 1; j <= n - 1 && d <= tt; j++)
27             {
28                 has_train[d][j][0] = true;
29                 d += t[j];
30             }
31         }
32         cin >> m2;
33         while (m2--)
34         {
35             cin >> d;
36             for (int j = n; j >= 2 && d <= tt; j--)
37             {
38                 has_train[d][j][1] = true;
39                 d += t[j - 1];
40             }
41         }
42 
43         //初始化dp数组
44         for (int i = 1; i <= n; i++)
45             dp[tt][i] = inf;
46         dp[tt][n] = 0;
47 
48         for (int i = tt - 1; i >= 0; i--)
49         {
50             for (int j = 1; j <= n; j++)
51             {
52                 dp[i][j] = dp[i + 1][j] + 1; //+1s
53                 if (i + t[j] <= tt && j + 1 <= n && has_train[i][j][0])
54                     dp[i][j] = min(dp[i][j], dp[i + t[j]][j + 1]); //向右走
55                 if (i + t[j - 1] <= tt && j - 1 >= 1 && has_train[i][j][1])
56                     dp[i][j] = min(dp[i][j], dp[i + t[j - 1]][j - 1]); //向左走
57             }
58         }
59         if (dp[0][1]<inf)
60             cout << "Case Number " << cnt << ": " << dp[0][1] << endl;
61         else
62             cout << "Case Number " << cnt << ": impossible" << endl;
63         cnt++;
64     }
65     return 0;
66 }

 

【luogu2583】地铁间谍


联系
我们