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

UVA1025 城市里的间谍 A Spy in the Metro

（本题有多倍经验哦）

一. 思路

1. 思考解法

• 时间 是个好的 DP 阶段，时间轴上靠后发生的不会影响前面的事，反映到本题上就是 Maria 之后怎么走不会影响现在的最优解，符合无后效性。

• Maria 既可以乘向东的地铁，又可以乘向西的地铁，还可以呆着不动。那么一种情况可以由多种情况而来，多种情况也可以发展成一种情况，各种情况互相交织，符合子问题重叠性。

所以考虑 DP。

2. 前缀和初始化

题目给出了站的时间间距和每列地铁发车时的时间（只会从首末两站发车），事实上，地铁在前进中到达每站的时间就是个前缀和 （偷偷点开标签我们也可以看到前缀和），到达某站的时间就是前面所有站时间间距之和，当然还要加上发车时间。

3. DP

我采用的是 刷表法，当然，填表法 也可以。

1. 所需条件：

   • $stabet_i$：站 $i-1$ 与站 $i$ 间相隔的时间。

   • $canright_{i,j}(canleft_{i,j})$：$i$ 时刻 $j$ 站是否有开向末站（首站）的火车。

   • $d_{i,j}$：得到 $i$ 时刻在 $j$ 站这种状态最少的停留时间。

   通过前缀和我们已经得到 $canright$ 以及$canleft$ 数组。接下来就是状态转移了。

2. 初始状态：

   易得，应初始化为： $d_{i,j}=\begin{cases}0&(i=0~\land~j=1)\\\infty&(else)\end{cases}$

   其中 $\infty$ 代表无法到达。

3. 状态转移：

   因为本题的阶段之间不像普通的0/1背包那样只会由上一阶段转移到，而是也会由很多个单位时间之前的阶段转移到（站与站之间的时间不止1），所以我选择多维数组而非滚动数组。

   首先，无论此刻此站有没有地铁，都可以在本站等待，这是普遍的转移；另外，如果此刻此站恰好有地铁，可以做特殊的转移。

   综上所述，状转方程：（因为是刷表法，状转方程不方便写在一个括号里，蒟蒻就这么写了 qwq）

   （$\operatorname{self}$ 代表自己）

   $$\begin{aligned} &d_{i,j}=\min(\operatorname{self},~d_{i-1,j}+1)&(i>0) \\ &d_{i+stabet_{j+1},j+1}=\min(\operatorname{self},~d_{i,j})&(canright_{i,j}=true) \\ &d_{i+stabet_j,j-1}=\min(\operatorname{self},~d_{i,j})&(canleft_{i,j}=true) \\ \end{aligned}$$

4. 结果状态：

   $d_{T,n}$

二. 代码

#include<bits/stdc++.h>
using namespace std;
const int MAXn = 50;
const int MAXT = 2000;
const int INF = 0x3f3f3f3f;

template <class T> 
inline void read(T &a) {
    register char c;while (c = getchar(), c < '0' || c > '9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9')x = (x << 1) + (x << 3) + c - '0';a = x;  
}

int n, T, stabet[MAXn + 10], rightcnt, leftcnt;	
bool canright[MAXT + 10][MAXn + 10], canleft[MAXT + 10][MAXn + 10];	 
int d[MAXT + 10][MAXn + 10];										

int main() {
    int k = 0;
    read(n);
    while (n) {
        ++k;
        memset(canright, 0, sizeof(canright));	// 
        memset(canleft, 0, sizeof(canleft));	//多组数据要初始化
        memset(d, 0x3f, sizeof(d));				//
        read(T);
        for (int i = 2; i <= n; ++i) {
            read(stabet[i]);
        }
        int time;								//
        read(rightcnt);							//
        for (int i = 1; i <= rightcnt; ++i) {	// 
            read(time);							//
            canright[time][1] = 1;				//
            for (int j = 2; j <= n; ++j) {		//
                time += stabet[j];				//
                canright[time][j] = 1;			//
            }									//
        }										//边读入边用前缀和计算canright和canleft数组
        read(leftcnt);							//
        for (int i = 1; i <= leftcnt; ++i) {	//
            read(time);							//
            canleft[time][n] = 1;				//
            for (int j = n - 1; j >= 1; --j) {	//
                time += stabet[j + 1];			//
                canleft[time][j] = 1;			//
            }									//
        }										//
        d[0][1] = 0;
        for (int i = 0; i <= T; ++i) {												//
            for (int j = 1; j <= n; ++j) {											//
                if (i)																//
                    d[i][j] = min(d[i][j], 											//
                                  d[i - 1][j] + 1);									//
                if (canright[i][j])													//
                    d[i + stabet[j + 1]][j + 1] = min(d[i + stabet[j + 1]][j + 1], 	//动态规划 
                                                      d[i][j]					  );//
                if (canleft[i][j])													//
                    d[i + stabet[j]][j - 1] = min(d[i + stabet[j]][j - 1], 			//
                                                  d[i][j]				  );		//
            }																		//
        }																			//
        if (d[T][n] == INF) {
            printf("Case Number %d: impossible\n", k);
        } else {
            printf("Case Number %d: %d\n", k, d[T][n]);
        }
        read(n);	
    }	
}