UVa1025

r囧r小猫 2021-12-24 06:33 109阅读 0赞

## 题意： 某城市的地铁是线性的，有n（2≤n≤50）个车站，从左到右编号为1～n。有M1辆列车从第1站开始往右开，还有M2辆列车从第n站开始往左开。在时刻0，Mario从第1站出发，目的是在时刻T（0≤T≤200）会见车站n的一个间谍。在车站等车时容易被抓，所以她决定尽量躲在开动的火车上，让在车站等待的总时间尽量短。列车靠站停车时间忽略不计，且Mario身手敏捷，即使两辆方向不同的列车在同一时间靠站，Mario也能完成换乘。    输入第1行为n，第2行为T，第3行有n－1个整数t1,t2,…,tn−1（1≤ti≤70），其中ti表示地铁从车站i到i＋1的行驶时间（两个方向一样）。第4行为M1（1≤M1≤50），即从第1站出发向右开的列车数目。第5行包含M1个整数d1, d2,…, dM1（0≤di≤250，di＜di+1），即各列车的出发时间。第6、7行描述从第n站出发向左开的列车，格式同第4、5行。输出仅包含一行，即最少等待时间。无解输出impossible。    分析：时间是单向流逝的，是一个天然的“序”。影响到决策的只有当前时间和所处的车站，所以可以用d(i,j)表示时刻i，你在车站j（编号为1～n），最少还需要等待多长时间。边界条件是d(T,n)=0，其他d(T,i)（i不等于n）为正无穷。有如下3种决策。 ##

## 决策1：等1分钟。   决策2：搭乘往右开的车（如果有）。   决策3：搭乘往左开的车（如果有）。   在程序中定义一个数组has\_train。has\_train\[t\]\[i\]\[0\]表示时刻t，在车站i是否有往右开的火车，has\_train\[t\]\[i\]\[1\]类似，不过记录的是往左开的火车。状态有O(nT)个，每个状态最多只有3个决策，因此总时间复杂度为O(nT)。 ##

## ——摘自《算法竞赛入门经典（第2版）P268》 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    int n,T,m1,m2,t[100],d[100],has_train[1000][100][2],dp[1000][100];
    const int INF = 1e9;
    int main() {
        int cas=1;
        while(~scanf("%d",&n)&&n) {
            memset(has_train,0,sizeof(has_train));
            memset(dp,0,sizeof(dp));
            memset(t,0,sizeof(t));
            scanf("%d",&T);
            for(int i=1;i<n;i++) scanf("%d",&t[i]);
            scanf("%d",&m1);
            for(int i=1;i<=m1;i++) {
                scanf("%d",&d[i]);
                int k=d[i];
                for(int j=1;j<n;j++) {
                    has_train[k][j][0]=1;
                    k+=t[j];
                }
            }
            scanf("%d",&m2);
            for(int i=1;i<=m2;i++) {
                scanf("%d",&d[i]);
                int k=d[i];
                for(int j=n;j>1;j--) {
                    has_train[k][j][1]=1;
                    k+=t[j-1];
                }
            }
            for(int i=1;i<=n-1;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: ",cas++);
            if(dp[0][1]>=INF) printf("impossible\n");
            else printf("%d\n",dp[0][1]);
        }
        return 0;
    }