[SCOI2012]喵星人的入侵题解

Illusory_dimes · 2022-05-16 20:21:43 · 题解

（思路大量参考 DP 带师 UM 的博客）

一个能直接把人干劝退的插头 DP 。。

Description

给定一个 n * m 图，有一个起点和终点和一些空地，你需要在空地上放置一些障碍和不超过 k 个炮台（均不可经过），使得：

起点和终点仍连通，可以存在多条路径；
每经过一个点（起终也算），答案加上该点八连通的炮台数，最大化答案（注：多条路径算答案最小的一条）。

\min(n,\ m) \leq 6,\ \max(n,\ m) \leq 20,\ 1\leq k \leq 15

Analysis

这个数据就很插头 DP 把，那就不去想其他的了。

那既然是要路径（不是回路），那自然一行的状态就直接 0 表示无插头， 1 表示左插头， 2 表示右插头， 3 表示独立插头。

但是这样好像不太够，因为考虑到八连通下的贡献，需要知道附近几个点的状态，是路径，是炮台还是障碍。

所以需要一行状态形如（粉色那一列）：

对于打叉的点，记录的就是这些格子是路径，是炮台还是障碍（其他还有四个格子因为那个点还没遍历到，不考虑）。

（这两个都四进制就行，注：之后插头的叫状态 1 ，格子种类的叫状态 2 ）

还不够，因为有炮台的限制，所以还要加一个指炮台数量（最多 15 个所以二进制 4 位就够了）。

Solution

根据 Analysis 里说的，对于每个点，我们提取上一行状态 1 的左格 pr 和上格 pd ，状态 2 的左格 l ，左上格 ul ，上格 u ，右上格 ur 。

啊啊啊，** 大力分讨！！（推荐画图食用）

如果左，上都是路径但是都不是插头，说明这个地方不能再有路径接上去了，要么放障碍，要么放炮台。（也就这种情况是和状态 2 有关的）
这个点本来就是障碍点，那也就只有左，上均没有插头的时候能转移。
起点或终点（可以形象化成一个独立插头）

①. 均没有插头

直接新建独立插头。

②. 无插头 + 左插头（或左 + 无）

删除当前插头，并且把对应的右插头改成独立插头。

③. 无插头 + 右插头（或右 + 无）

删除当前插头，并且把对应的左插头改成独立插头。

④. 无插头 + 独立插头（或独立 + 无）

删除当前插头，没对应的插头，所以没了。
空地（插头种类不定，跟着之前的走就行）

①. 均没有插头

可以选择放障碍，放炮台，或者开一个新路径。

②. 仅有一个有插头

跟着插头走就行了。

③. 都是左插头

删除这两个插头，并且把上格插头对应的右插头变成左插头。

④. 都是右插头

删除这两个插头，并且把左格插头对应的左插头变成右插头。

⑤. 右插头 + 左插头

删除这两个插头，并且把对应的两个插头左右不变。

⑥. 左插头 + 右插头

不合法，这样就是闭合回路。

⑦. 左插头 + 独立插头（或独立 + 左）

删除这两个插头，并且把对应的右插头变成独立插头。

⑧. 右插头 + 独立插头（或独立 + 右）

删除这两个插头，并且把对应的左插头变成独立插头。

⑨. 独立插头 + 独立插头

直接删除，没什么能伸展出去的。

接下来，来想想怎么计算答案。

前面提到过，处理这个点的时候我们只知道周围四个点的状态。

那丢掉的四个点怎么办呢？在处理那四个点的时候自然就会算当前这个点了。正好，还不会算重。

因为相当于我们全部认定这个空地就是路径，那么他的贡献就是周围八个格子炮台数。转化一下也就是炮台的贡献就是周围八个格子空地数。

所以如果是炮台，就算已知的四个点里面空地数；

所以如果是空地，就算已知的四个点里面炮台数。

那不是还有多条路径算最小值的限制吗？

那你把答案最大的那条留下，剩下的直接全部用障碍填满，答案肯定不劣，况且这一定会在状态中出现，所以可以覆盖掉多条路径的影响。

那全部答案取合法里面的最大值就行了。

Code

/*

*/
#include <bits/stdc++.h>
//#define int long long
#define BT1 ((l == 1) + (ul == 1) + (u == 1) + (ur == 1))
#define BT3 ((l == 3) + (ul == 3) + (u == 3) + (ur == 3))
using namespace std;
typedef long long ll;
const int N = 24, zs = 299987;
int n, m, K, a[N][N], p, las, fst[zs + 10], tot[2], ans, inc[N], pl[N];
struct BIT {
    int c0, c1, c2;
    bool operator == (const BIT &it) const {
        return (c0 == it.c0) && (c1 == it.c1) && (c2 == it.c2);
    }
};
struct mdzz {int nxt, val[2]; BIT bt[2];} e[(1 << 24) + 10];
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') w = -1; ch = getchar();}
    while (isdigit(ch)) {s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar();}
    return s * w;
}
inline void insert(int c0, int c1, int c2, int num) {
    int u = ((((1ll * c0 << 16) | c1) << 4) | c2) % zs + 1;
    for (int i = fst[u]; i; i = e[i].nxt) {
        if (e[i].bt[p] == (BIT) {c0, c1, c2}) {
            e[i].val[p] = max(e[i].val[p], num);
            return ;
        }
    }
    e[++tot[p]].nxt = fst[u];
    e[tot[p]].bt[p] = (BIT) {c0, c1, c2};
    e[tot[p]].val[p] = num;
    fst[u] = tot[p];
}
int pr, pd, l, ul, u, ur, c0, c1, c2;
inline int RT(int c0, int j, int pm) {
    int tot = 1, x = c0, lm;
    while (2333) {
        lm = (x >> pl[j]) & 3;
        if (lm == 1) ++tot; else if (lm == 2) --tot;
        if (!tot) return c0 ^ (lm << pl[j]) ^ (pm << pl[j]);
        ++j;
    }
    return 0;
}
inline int LT(int c0, int j, int pm) {
    int tot = 1, x = c0, lm;
    while (2333) {
        lm = (x >> pl[j]) & 3;
        if (lm == 2) ++tot; else if (lm == 1) --tot;
        if (!tot) return c0 ^ (lm << pl[j]) ^ (pm << pl[j]);
        --j;
    }
    return 0;
}
inline void Plugdp(int i, int j, BIT bit, int num) {
    //这里的c0是已经把左和上去掉的残缺状态
    //这里的c1是已经把左上去掉的残缺状态
    if ((!pr && l == 1) || (!pd && u == 1)) {
        if (pr || pd) return ;
        insert(c0, c1, c2, num);
        if (c2 < K && a[i][j] == 1) {
            insert(c0, c1 ^ (3 << pl[j]), c2 + 1, num + BT1);
        }
    }
    else if (a[i][j] == 2) {
        if (!pr && !pd) insert(c0, c1, c2, num);
    }
    else if (a[i][j] == 1) {
        if (!pr && !pd) {
            insert(c0, c1, c2, num);
            if (c2 < K) insert(c0, c1 ^ (3 << pl[j]), c2 + 1, num + BT1);
            insert(c0 ^ inc[j - 1] ^ (inc[j] << 1), c1 ^ inc[j], c2, num + BT3);
        }
        else if (!pr || !pd) {
            insert(c0 ^ ((pd | pr) << pl[j - 1]), c1 ^ inc[j], c2, num + BT3);
            insert(c0 ^ ((pd | pr) << pl[j]), c1 ^ inc[j], c2, num + BT3);
        }
        else if (pr == 1 && pd == 1) insert(RT(c0, j - 1, 1), c1 ^ inc[j], c2, num + BT3);
        else if (pr == 2 && pd == 2) insert(LT(c0, j - 1, 2), c1 ^ inc[j], c2, num + BT3);
        else if (pr == 2 && pd == 1) insert(c0, c1 ^ inc[j], c2, num + BT3);
        else if (pr == 1 && pd == 2) ;
        else if (pr == 1 && pd == 3) insert(RT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3);
        else if (pr == 3 && pd == 1) insert(RT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3);
        else if (pr == 2 && pd == 3) insert(LT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3);
        else if (pr == 3 && pd == 2) insert(LT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3);
        else if (pr == 3 && pd == 3) insert(c0, c1 ^ inc[j], c2, num + BT3);
    }
    else if (a[i][j] == 3 || a[i][j] == 4) {
        if (!pr && !pd) {
            insert(c0 ^ (3 << pl[j - 1]), c1 ^ inc[j], c2, num + BT3);
            insert(c0 ^ (3 << pl[j]), c1 ^ inc[j], c2, num + BT3);
        }
        else if (!pr && pd == 1) insert(RT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3);
        else if (pr == 1 && !pd) insert(RT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3);
        else if (!pr && pd == 2) insert(LT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3);
        else if (pr == 2 && !pd) insert(LT(c0, j - 1, 3), c1 ^ inc[j], c2, num + BT3);
        else if (pr == 3 && !pd) insert(c0, c1 ^ inc[j], c2, num + BT3);
        else if (!pr && pd == 3) insert(c0, c1 ^ inc[j], c2, num + BT3);
    }
}
inline void plug() {
    tot[p] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1, x; j <= tot[p]; ++j) {
            e[j].bt[p].c0 <<= 2;
            x = e[j].bt[p].c1;
            (e[j].bt[p].c1 ^= ((x >> pl[m + 1]) & 3) << pl[m + 1]) <<= 2;
        }
        for (int j = 1; j <= m; ++j) {
            memset(fst, 0, sizeof(fst));
            swap(las, p); tot[p] = 0;
            for (int k = 1, num; k <= tot[las]; ++k) {
                BIT bit = e[k].bt[las]; num = e[k].val[las];
                if (bit.c0 >= inc[m + 1]) continue;
                c0 = bit.c0; c1 = bit.c1; c2 = bit.c2;
                pr = (c0 >> pl[j - 1]) & 3; pd = (c0 >> pl[j]) & 3;
                l = (c1 >> pl[j - 1]) & 3; ul = (c1 >> pl[j]) & 3;
                u = (c1 >> pl[j + 1]) & 3; ur = (c1 >> pl[j + 2]) & 3;
                c0 ^= (pr << pl[j - 1]) ^ (pd << pl[j]); c1 ^= (ul << pl[j]);
                Plugdp(i, j, bit, num);
            }
        }
    }
}
inline int pdd(char ch) {
    if (ch == '.') return 1;
    if (ch == '#') return 2;
    if (ch == 'S') return 3;
    if (ch == 'T') return 4;
    if (ch == 'X') return 5;
    return 0;
}
int main() {
    n = read(); m = read(); K = read();
    inc[0] = 1; las = 1;
    for (int i = 1; i <= 14; ++i) {
        inc[i] = inc[i - 1] << 2, pl[i] = i << 1;
    }
    if (n >= m) {
        char ch;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                ch = getchar();
                while (!(a[i][j] = pdd(ch))) ch = getchar();
            }
        }
    }
    else {
        swap(n, m);
        char ch;
        for (int j = 1; j <= m; ++j) {
            for (int i = 1; i <= n; ++i) {
                ch = getchar();
                while (!(a[i][j] = pdd(ch))) ch = getchar();
            }
        }
    }
    plug();
    for (int i = 1; i <= tot[p]; ++i) {
        if (!e[i].bt[p].c0) ans = max(ans, e[i].val[p]);
    }
    printf("%d\n", ans);
    return 0;
}

[SCOI2012]喵星人的入侵 题解

Description

Analysis

Solution

Code

[SCOI2012]喵星人的入侵题解