题解 AT2669 【[AGC017F] Zigzag】

· · 题解

在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/AGC017.html。

我们考虑从左到右，依次确定每条折线的形态。

如果直接状压 DP，每次转移一条线，可以做到 \mathcal O (4^N \operatorname{poly}(N))。

哎，你有没有想到，当你做在 M 行 N 列的网格上摆棋子的那种题目时，也就是传统状压 DP 题：
一行一行转移，也是复杂度较劣的。那样虽然阶段数是 \mathcal O (M)，但是状态数和每个状态的转移数都是 \mathcal O (2^N) 的。
但是我们有「轮廓线 DP」啊！也就是每次只在一行往前推一格，这样虽然阶段数是 \mathcal O (M N) 的，但是转移数是 \mathcal O (1) 的。
也就做到了 \mathcal O (2^N M N) 的复杂度。

其实这个思想也能用到这题上，如果你也先按照折线从左到右，再按照每条折线从上到下依次确定：
因为上一条折线中，比当前位置往起点的部分其实是不需要了，所以可以不记那些状态（参考轮廓线 DP 时上一层状态）。
此时阶段数为 \mathcal O (M N)，但是还需记一个状态，也就是上一条折线在此时的高度时的水平坐标，这是 \mathcal O (N) 的。
而转移是 \mathcal O (1) 的，综合来看总复杂度是 \mathcal O (2^N M N^2) 的。还是过不去。

我们需要最后一个优化：把记录上一条折线在此时的高度时的水平坐标这一个信息去掉。

注意如果在此时的高度时，上一条折线比这条折线的水平位置严格靠左，那么这个点其实是毫无意义的。

实际上所有这条折线永远都走不到的地方，都是无意义的。

也就是说上一条折线，太靠左了的话，有一部分信息是没必要的。

那么我们把上一条折线右侧的区域，和这条折线未来可能走到的区域，取个交，也无妨。

这样也就是说上一条折线是直接从当前位置出发的了，而当前位置可以直接由这条折线之前的路径确定。

这样就成功去掉一个 \mathcal O (N) 的状态了，转移仍然是 \mathcal O (1) 的。

仅有上一条折线往左，而这条折线想往右时，需要把上一条折线多余的部分抹掉，变成从当前点出发的样子。

时间复杂度为 \mathcal O (2^N M N)。

#include <cstdio>

const int Mod = 1000000007;
const int MN = 20, MM = 20;

inline void Add(int &x, int y) { x -= Mod - y; x += x >> 31 & Mod; }

int N, M, K, t[MM][MN];
int f[2][1 << MN];

int main() {
    scanf("%d%d%d", &N, &M, &K), --N;
    for (int i = 0; i < M; ++i)
        for (int j = 0; j < N; ++j)
            t[i][j] = -1;
    for (int i = 1; i <= K; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        t[--a][--b] = c;
    }
    int o = 0;
    f[o][0] = 1;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            o ^= 1;
            for (int S = 0; S < 1 << N; ++S) f[o][S] = 0;
            for (int S = 0; S < 1 << N; ++S) if (f[o ^ 1][S]) {
                int v = f[o ^ 1][S];
                if (t[i][j] != 1) {
                    if (~S >> j & 1) Add(f[o][S], v);
                }
                if (t[i][j] != 0) {
                    if (S >> j & 1) Add(f[o][S], v);
                    else {
                        int T = S >> j;
                        if (T) T &= T - 1;
                        T = (T + 1) << j | (S & ((1 << j) - 1));
                        Add(f[o][T], v);
                    }
                }
            }
        }
    }
    int Ans = 0;
    for (int S = 0; S < 1 << N; ++S) Add(Ans, f[o][S]);
    printf("%d\n", Ans);
    return 0;
}