(UVa1025) 地铁里的间谍 (A Spy in the Metro)

发表于 分类于 ，

一道经典题 ## 题目描述:

某城市的地铁只有一条线路，有 n 个车站 (n<=50), 有 M1 辆列车从 1 号站往右开，M2 辆列车从 n 号站往左开

间谍 Mario 从 1 号站出发， 要在时刻 T (T<=200) 会见在 n 站的一个间谍， 给出地铁的发车时刻和相邻两个站之间的行驶时间， 求 Mario 在车站上的最少等待时间 (无解输出”impossible”)

思路:

以时间为序的多阶段 dp

设 d (i,j) 是间谍 Mario 在车站 i, 时刻 j 的最小等待时间

则答案为 d (n,T), 初始化 d (0,0)=0, 其它 d 为无穷大， 若 d (n,T) 等于无穷大无解

状态转移方程见代码:

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int Mn(55);
const int Mt(205);
int d[Mn][Mt];
int dis[Mn]; //相邻两车站间距离
bool ist[Mn][Mt][2]; //车站i,时刻j是否有车(0:右驶,1:左驶)
int main()
{
    int n,cs(0);
    while(scanf("%d",&n)==1 && n!=0)
    {
        int T; scanf("%d",&T);
        memset(dis,0,sizeof dis);
        for(int i(1);i<n;++i)
            scanf("%d",&dis[i]);
        memset(ist,0,sizeof ist);
        int m1,m2;
        scanf("%d",&m1);
        for(int i(1);i<=m1;++i)
        {
            int t;
            scanf("%d",&t);
            ist[1][t][0] = true;
            for(int j(1);j<n;++j)
                ist[j+1][t+=dis[j]][0] = true;
        }
        scanf("%d",&m2);
        for(int i(1);i<=m2;++i)
        {
            int t;
            scanf("%d",&t);
            ist[n][t][1] = true;
            for(int j(n-1);j>=1;--j)
                ist[j][t+=dis[j]][1] = true;
        }
        memset(d,0x3f,sizeof d);
        d[1][0] = 0;
        for(int j(1);j<=T;++j)
        {
            for(int i(1);i<=n;++i)
            {
                if(i>1 && ist[i][j][0] && j>=dis[i-1])	d[i][j] = min(d[i][j],d[i-1][j-dis[i-1]]); //如果有向右驶的车
                if(i<n && ist[i][j][1] && j>=dis[i])	d[i][j] = min(d[i][j],d[i+1][j-dis[i]]); //如果有向左驶的车
                d[i][j] = min(d[i][j],d[i][j-1]+1); //等待
            }
        }
        printf("Case Number %d: ",++cs);
        if(d[n][T]==0x3f3f3f3f) cout << "impossible\n";
        else        cout << d[n][T] << endl;
    }
    return 0;
}