Codeforces 1840F Railguns

题目来自 Codeforces Round #878 (Div.3) F。link

  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!

Problem Description

在 \(t=0\) 秒，玩家在 \((0,0)\)。玩家的目的地在右下角 \((n,m)\) \((1\leq n\cdot m\leq 10^4)\)。每一秒，玩家可以：(1) 向右移动 (2) 向下移动 (3) 原地不动。

除此之外，有 \(r\) (\(1\leq r \leq 100\)) 个轨道炮，第 \(i\) 个轨道炮将在 \(t=t_i\) 秒对第 \(p_i\) 行或第 \(q_i\) 列进行打击。

玩家由 \((0,0)\) 活着到达 \((n,m)\)，至少需要多少秒？若不可能活着到达目的地，输出 \(-1\)。

Tutorial

只打了 \(O(nmt)\) 的暴力 DP，其实看到数据规模后就应该想到正确的解法应该是 \(O(nmr)\) 的……

如果玩家不能选择原地不动，那么 DP 的设计相对比较简单：\(dp[x][y]\) 代表玩家是否能活着到达 \((x,y)\)。若 \(dp[x][y]=1\)，则活着到达 \((x,y)\) 的最少时间为 \(x+y\)；否则无法活着到达 \((x,y)\)。

如果在第 \(t=x+y\) 秒存在某个轨道炮的攻击范围覆盖到坐标 \((x,y)\)，则 \(dp[x][y]=0\)；否则进行状态转移 \(dp[x][y]=dp[x-1][y] \lor dp[x][y-1]\)。

接下来考虑玩家可以选择原地不动的情况。

首先观察到一个事实，若存在一条从 \((0,0)\) 到 \((n,m)\) 的合法轨迹，那么玩家选择原地不动的次数不会超过 \(r\)。无论是向右还是向下，它们均能对「到达目的地」作出贡献，而选择原地不动则不行；选择原地不动的唯一理由是为了「躲避轨道炮」。在最极端的情况下，对于每次轨道炮袭击，玩家均选择留在安全的原地进行躲避，此时玩家选择原地不动的次数也才达到 \(r\)；超过 \(r\) 次的原地不动是没有意义的。

另外，我们将注意到玩家原地不动的次数越少，其到达 \((n,m)\) 的时间越短。结合上述事实有结论，玩家若能成功到达 \((n,m)\)，其到达 \((n,m)\) 的时间不会超过 \(n+m+r\)。

基于这个结论，我们对上面提到的 DP 方案进行改进，增加一维状态标记到达 \((x,y)\) 选择原地不动的次数。 \(dp[x][y][z]\) 代表玩家原地不动了 \(z\) 次，是否能活着到达 \((x,y)\)。若 \(dp[x][y][z]=1\)，则原地不动 \(z\) 次活着到达 \((x,y)\) 的最少时间为 \(x+y+z\)；否则无法在原地不动 \(z\) 次的情况下活着到达 \((x,y)\)。

如果在第 \(t=x+y+z\) 秒存在某个轨道炮的攻击范围覆盖到坐标 \((x,y)\)，则 \(dp[x][y][z]=0\)；否则进行状态转移 \(dp[x][y][z]=dp[x-1][y][z]\lor dp[x][y-1][z] \lor dp[x][y][z-1]\)。

总状态数 \(nmr=10^4\cdot 100=10^6\)，绰绰有余。

Eureka moment!

本题可以等价为这样一个问题：给定 \(n,m\)，在一个三维空间里，玩家需要由 \((0,0,0)\) 到达 \((n,m,z)\)；存在轨道炮在特定的时间攻击平面 \(x=p\) 或 \(y=q\)。求最小的可以活着到达的 \(z\) 坐标。

\(z\) 坐标代表的是原地不动的次数，但它也是唯一一个决定了时间的变量。这是因为由 \(x=0,y=0\) 到达 \(x=n,y=m\) 所需的时间是固定的 \(n+m\)。玩家选择原地不动，相当于其向 \(z\) 轴往上移动了一个单位。

Code Implementation

读入的数据很多，不开快读会 TLE。懒得写快读，解除 cin 同步后也过了。

注意对轨道炮的处理，使用的是辅助数组 die。不是很符合直觉的处理方式，但是理解了「玩家原地不动的次数不会超过 \(r\)」这一事实后就很好懂了。

#include <iostream>
#include <cstring>

using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        int n, m, r;
        cin >> n >> m >> r;

        bool die[n + 1][m + 1][r + 1];   
        // auxilary array: die[x][y][z] means if not moving for z times
        //                 character will or will not be attacked in (x, y)
        memset(die, 0, sizeof die);
        for (int i = 1; i <= r; ++i) {
            int t, d, p;
            cin >> t >> d >> p;
            if (d == 1) {
                for (int col = 0; col <= m; ++col) {
                    int z = t - p - col;
                    if (z >= 0 && z <= r)
                        die[p][col][z] = true;    
                        // die[x][y][z] is true only when x+y+z=t_i for some railgun t_i
                }
            }
            if (d == 2) {
                for (int row = 0; row <= n; ++row) {
                    int z = t - row - p;
                    if (z >= 0 && z <= r)
                        die[row][p][z] = true;
                }
            }
        }

        bool dp[n + 1][m + 1][r + 1];
        // dp array: dp[x][y][z] means if not moving for z times
        //           character will or will not successfully reach (x, y)
        memset(dp, 0, sizeof dp);
        dp[0][0][0] = 1;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                for (int z = 0; z <= r; ++z) {
                    if (!die[i][j][z]) {
                        if (i > 0)
                            dp[i][j][z] |= dp[i - 1][j][z];
                        if (j > 0)
                            dp[i][j][z] |= dp[i][j - 1][z];
                        if (z > 0)
                            dp[i][j][z] |= dp[i][j][z - 1];
                    }
                }
            }
        }
        int ans = -1;
        for (int z = r; z >= 0; --z) {
            if (dp[n][m][z])
                ans = n + m + z;
        }
        cout << ans << endl;
    }


    return 0;
}