UVA 1025 A Spy in the Metro城市里的间谍（dp）

野性酷女 2024-02-17 19:13 74阅读 0赞

分析：

d(i,j)表示时刻i在车站j，最少还需要等多长时间，

边界条件式是d(T,j)=0,其他为正无穷，每个站有3中决策

1：等待1分钟（为什么是一分钟？因为最小单位是一分钟）

2：搭乘往右开的车

3：塔乘往左开的车

预处理数组has\_train\[t\]\[j\]\[\],在时间t、j站是否有向左（或右的地铁），输入时进行处理。时间逆序列举。

AC代码如下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define INF 1e5
    int N,T;
    int has_train[200+10][50+3][2];
    int t[50+3];
    int dp[200+10][50+3];
    int main(){
    	int count1=0;
    	while(scanf("%d",&N)==1 && N){
    		scanf("%d",&T);
    		memset(t,0,sizeof(t));
    		for(int i=1;i<N;i++)scanf("%d",&t[i]);
    		memset(has_train,0,sizeof(has_train));
    		int M1;
    		scanf("%d",&M1);
    		for(int i=0;i<M1;i++){
    			int d;
    			scanf("%d",&d);
    			for(int j=1;j<=N;j++)
    			{if(d>T)break;
    			has_train[d][j][0]=1;
    			d+=t[j];
    			}
    		}
    		int M2;
    		scanf("%d",&M2);
    		for(int i=0;i<M2;i++){
    			int d;
    			scanf("%d",&d);
    			for(int j=N;j>=1;j--)
    			{if(d>T)break;
    			has_train[d][j][1]=1;
    			d+=t[j-1];
    			}
    		}
    		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)
    				dp[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)
    				dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]); //向左 
    			}
    		}
    		printf("Case Number %d: ",++count1);
    		if(dp[0][1]>=INF)printf("impossible\n");
    		else printf("%d\n",dp[0][1]);
    	}
    	return 0;
    }