P2583 A Spy in the Metro

· · 题解

这道题似乎还是 ICPC 2003 决赛的题呢，但是过了 20 年现在来看就是一道非常经典的 DP 了。

题目分析

既然是做 DP ，我们就应该知道他的几个要素：阶段、状态、以及状态之间的转移。

对于这道题来说，其状态是什么呢？我们首先想到的是车站，还有一个就是时间，时间是单向流逝的。我们可以用一个二维数组 dp_{i,j} 来表示时间 i 位于车站 j 要在地铁站等几分钟这个状态。

然后是状态转移。最终状态 dp_{T,N} 我们是知道的，它一定等于 0，否则玛丽亚就不能与另一个间谍碰头了。那我们如何将 dp_{T,N} 这个状态转移到 dp_{0,1} 这个状态呢？

对于一个状态，我们只有三种决策：

  1. 原地等待一分钟: dp_{i,j} = dp_{i+1,j} + 1

  2. 如果有向左开的车，我们可以乘搭向左的车: dp_{i,j} = \min (dp_{i,j}, dp_{{i+t_j},{j+1}})

  3. 如果有向右开的车，我们可以乘搭向右开的车: dp_{i,j} = \min( dp_{i,j}, dp_{i+t_{j-1},j-1} )

一些代码实现

如何判断是否有向左向右开的车呢？输入时预处理即可：

    while(M1--){//向右开 
    int d = read(), tm = 0;
    tm = d;
    for(int j = 1; j <= N; j++){
        pd[tm][j][0] = 1;
        tm += t[j];
        }
    }
    int M2 = read();
    while(M2--){//向左开 
        int d = read(), tm = 0;
        tm = d;
        for(int j = N; j >= 1; j--){
            pd[tm][j][1] = 1;
            tm += t[j-1];
        }
    }

DP 时可以从后往前递推，其中一些变量名可以到后面的完整代码那去看一下：

memset(dp, 0x3f, sizeof(dp));
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 && pd[i][j][0] && i + t[j] <= T) dp[i][j] = min(dp[i][j], dp[i+t[j]][j+1]);//乘搭向右开的车
        if(j > 1 && pd[i][j][1] && i + t[j-1] <= T) dp[i][j] = min(dp[i][j], dp[i + t[j-1]][j-1]);//乘搭向左开的车

    }
}

最后输出时要按他的格式输出，注意判断是否可能，不可能要输出 impossible 。

我们最终要的是 dp_{0,1} 即从 0 时刻在 1 车站在地铁站中暴露多长时间才能与间谍碰头

完整代码：

#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
inline int read(){
    int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } 
    while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } 
    return x * f ;
} 
int N, T;
int t[80];//从第i个车站到第i+1车站需要多长时间
int pd[2000][75][2];//在i时刻j车站是否有向右或左开的车
int dp[2000][75];
int cnt = 0;
int main(){
    while(N = read()){
        memset(pd, 0, sizeof(pd)), memset(t, 0, sizeof(t));
        T = read();
        for(int i = 1; i < N; i++) t[i] = read();
        int M1 = read();
        while(M1--){//右开 
            int d = read(), tm = 0;
            tm = d;
            for(int j = 1; j <= N; j++){
                pd[tm][j][0] = 1;
                tm += t[j];
            }
        }
        int M2 = read();
        while(M2--){//左开 
            int d = read(), tm = 0;
            tm = d;
            for(int j = N; j >= 1; j--){
                pd[tm][j][1] = 1;
                tm += t[j-1];
            }
        }
        memset(dp, 0x3f, sizeof(dp));//因为是要求最小值，所以将dp初始成极大值
        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 && pd[i][j][0] && i + t[j] <= T) dp[i][j] = min(dp[i][j], dp[i+t[j]][j+1]);//乘搭向右开的车
                if(j > 1 && pd[i][j][1] && i + t[j-1] <= T) dp[i][j] = min(dp[i][j], dp[i + t[j-1]][j-1]);//乘搭向左开的车

            }
        }
        cout << "Case Number " << ++cnt << ": ";
        if(dp[0][1] >= 0x3f) cout << "impossible" << endl;
        else cout << dp[0][1] << endl;
    }

}

完