自动搬运

查看原文

来自洛谷，原作者为

	djc AFO|渺渺兮予怀，望美人兮天一方

搬运于2025-08-24 21:39:19，当前版本为作者最后更新于2022-06-18 09:11:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题似乎还是 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;
	}
	
}

完