[動态規劃]【ACM/ICPC Word Finals 2003, UVa 1025】A Spy in the Metro 城市裡的間諜

題目描述

某城市地鐵是線性的,有n個車站,從左到右編号1-n。有M1輛列車從第1站開始往右開,還有M2輛列車從第n站開始往左開。在時刻0,Mario從第1站出發,目的在時刻T會見車站n的一個間諜。在車站等車時容易被抓，是以她決定盡量躲在開動的火車上,讓在車站等待的時間盡量短。列車靠站停車時間忽略不計,且Mario身手靈活,即時兩輛方向不同的列車在同一時間靠站,Mario也能完成換乘。

Input Data

輸入第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行。

Output Data

輸出僅包含一行，即最少等待時間。無解輸出impossible。

Input

4

55

5 10 15

4

0 5 10 20

4

0 5 10 15

4

18

1 2 3

5

0 3 6 10 12

6

0 3 5 7 12 15

2

30

20

1

20

7

1 3 5 7 11 13 17

Output

Case Number 1: 5

Case Number 2: 0

Case Number 3: impossible

——————————————分割の線————————————————

已知時間i，Mario停留在j站。不難發現Mario之前到達j站的路徑和時間與之後的決策并無關系，且決策僅與目前的時間和所處的車站有關。不妨用f[i][j]表示時刻i，Mario處于站台j時，最少還需要等待的時間。邊界為f[T][n]=0,f[T][i]=+∞;

存在三種決策：

1. 就地等一分鐘
2. 如果有車，搭乘向左開的車
3. 如果有車，搭乘向右開的車

在主過程上，運用填表法：

for(int i=T-;i>=;i--)
        {
            for(int j=;j<=n;j++)
            {
                f[i][j]=f[i+][j]+;
                if(j<n&&has_train[i][j][]&&i+t[j]<=T)
                    f[i][j]=min(f[i][j],f[i+t[j]][j+]);//right
                if(j>&&has_train[i][j][]&&i+t[j-]<=T)
                    f[i][j]=min(f[i][j],f[i+t[j-]][j-]);//left
            }
        }
           

此處運用has_train[t][i][0]表示時刻i，在站台j是否有向右的火車。has_train[t][i][0]與其類似，但是是記錄是否有向左開的火車。

我在輸入時進行處理：

memset(has_train,,sizeof(has_train));
        cin>>m1;
        for(int i=;i<=m1;i++)
        {
            int sum;
            scanf("%d",&sum);//讀入發車時間
            for(int j=;j<=n;j++)
            {
                has_train[sum][j][]=;//記錄在時刻sum站台j，有一輛向右開的火車
                sum+=t[j];//行駛到站台j+1的時間
            }
        }
        cin>>m2;
        for(int i=;i<=m2;i++)
        {
            int sum;
            scanf("%d",&sum);//讀入發車時間
            for(int j=n;j>=;j--)//由于是從右向左開，是以反向枚舉
            {
                has_train[sum][j][]=;//記錄在時刻sum站台j，有一輛向左開的火車
                sum+=t[j-];//行駛到站台j-1的時間
            }
        }
           

完整過程如下:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x11111111
int t[];
int f[][],has_train[][][];
int main()
{
    int n,T,m1,m2,cnt=,sick=;
    while(cin>>n&&n!=)
    {
        memset(t,,sizeof(t));
        memset(has_train,,sizeof(has_train));
        cnt++;
        cin>>T;
        for(int i=;i<n;i++)
            scanf("%d",&t[i]);//讀入從i到i+1的行駛時間，用t[i]表示
        cin>>m1;
        for(int i=;i<=m1;i++)
        {
            int sum;
            scanf("%d",&sum);//讀入發車時間
            for(int j=;j<=n;j++)
            {
                has_train[sum][j][]=;//記錄在時刻sum站台j，有一輛向右開的火車
                sum+=t[j];//行駛到站台j+1的時間
            }
        }
        cin>>m2;
        for(int i=;i<=m2;i++)
        {
            int sum;
            scanf("%d",&sum);//讀入發車時間
            for(int j=n;j>=;j--)//由于是從右向左開，是以反向枚舉
            {
                has_train[sum][j][]=;//記錄在時刻sum站台j，有一輛向左開的火車
                sum+=t[j-];//行駛到站台j-1的時間
            }
        }
        for(int i=;i<n;i++)
            f[T][i]=INF;
        f[T][n]=;//以上均為初始化
        for(int i=T-;i>=;i--)
        {
            for(int j=;j<=n;j++)
            {
                f[i][j]=f[i+][j]+;
                if(j<n&&has_train[i][j][]&&i+t[j]<=T)
                    f[i][j]=min(f[i][j],f[i+t[j]][j+]);//right
                if(j>&&has_train[i][j][]&&i+t[j-]<=T)
                    f[i][j]=min(f[i][j],f[i+t[j-]][j-]);//left
            }
        }
        printf("Case Number %d: ",cnt);
        if(f[][]>=INF) printf("impossible\n");//隻有時刻0并從站台1出發，才合法
        else printf("%d\n",f[][]);
    }
    return ;
}
           

狀态有O(nT)個，每個狀态最多隻有3個決策，是以總時間複雜度為O(nT).