AcWing 328. 芯片（二进制写法）

我自闭了，调了一下午，我居然认为 $2, 3$ 凑不出 $7$，我怕是个孤儿。

这是一位非要用二进制写的勇士。

首先定义状态 $S$，若 $S$ 的二进制第 $k$ 位为 $1$ 表示那一位下是空闲可以填数的。

再定义一个 $S(x)$ 表示 $S$ 下第 $x$ 位的值。

显然填 $2 * 3$ 小方格的时候，能不能填取决于最近的三行，和前面无关，我们搞一个二维二进制，通过转移达到目的。

$f[i][j][k] $ 为前 $i$ 行，第 $ i$ 行状态为 $j$，第 $i - 1$ 行状态为 $k$ 填的最多的小方格数。为什么要用空闲的状态状压而不是填过的呢？因为如果用填过的你不知道在上一行是不是已经填完了。。

转移 $f[i][j][k] = max( f[i - 1][p][q] + val(p, q, j, k))$。$val(p, q, j, k)$ 是两行状态转移的中，以 $i$ 行为

最下方填写的方格数。

显然复杂度爆炸，我们需要的是，压状态！压、压再压！！由于这是一个最优问题，所以我们可以剪枝，即保留的状态当且仅当里面的 $1$ （空闲位置）全部放上小方块，以这个原则进行剪枝，可以大大降低复杂度

对于一个状态 $k, j$ 考虑压掉不合法的状态
- $k(x) = 1, j(x) = 0$ 那个一永远放不上小方块
- $k(x) = 1, j(x) = 1$ 连续数量必须为偶数，因为到了 $2$ 个空闲还没扔掉意味着一定是要跨三行，这样列只能 $2$ 个。
- $k(x) = 0, j(x) = 1$ 连续数量必须 $> 1$
当 $m = 10$ 最坏情况下，合法的 $k, j$ 数量只有 $1123$ 个。
接着考虑合法的 $q, p$ → $k, j$ 的转移以及计算 $val$

转移的实质就是在 $j$ 这一行放可行的方块。
- 如果 $p(x) = k(x)$ 说明没放新的块，这种情况必须进行续传：
  - $p(x) = k(x) = 1$ 的情况，如果这时候 $q$ 必须是 $0$，$j$ 必须是 $1$（不能积累3个空闲块）
- 否则说明放了新的块
  - $p(x) = 0, k(x) = 1$，无中生有可还行（减掉
  - $q(x) = 0, p(x) = 1, k(x) = 0$，这时候 $j(x)$ 必须为 $0$ 并且连续块是 $3$ 的倍数（即放横着的块，贡献+）
  - $q(x) = 1, p(x) = 1, k(x) = 0$ 这时候 $j(x)$ 必须为 $0$ 且是偶数（放竖着的块，贡献+）

这样可以的匹配一共有 $5477$ 个（在 $m = 10$ 下）

跑的还是很快的 $740ms$

#include <cstdio>

#include <iostream>

#include <cstring>

#define x first

#define y second

using namespace std;

const int N = 150, S = 1130, M = 10, L = 5500;

typedef pair<int, int> PII;

int n, m, K, tot, cnt, o, f[N + 1][S], g[N + 1];

PII s[S];

struct Node{

    int a, b, c, y;

} d[L];

bool check(int k, int j) {

    int c1 = 0, c2 = 0;

    for (int i = 0; i < m; i++) {

        if ((k >> i & 1) && !(j >> i & 1)) return false;

        if ((k >> i & 1) && (j >> i & 1)) c2++;

        else {

            if (c2 & 1) return false;

            c2 = 0;

        }

        if (!(k >> i & 1) && (j >> i & 1)) c1++;

        else {

            if (c1 == 1) return false;

            c1 = 0;

        }

    }

    return !(c2 & 1) && (c1 != 1);

}

int get(int q, int p, int k, int j) {

    o = 0;

    int res = 0;

    for (int i = 0; i < m; i++) {

        if ((p >> i & 1) && (k >> i & 1)) {

            if (q >> i & 1 || i + 1 >= m) return -1;

            int u = i + 1;

            if ((q >> u & 1) || !(p >> u & 1) || !(k >> u & 1)) return -1;

            i = i + 1;

        }

        if (!(p >> i & 1) && (k >> i & 1)) return -1;

        if (!(q >> i & 1) && (p >> i & 1) && !(k >> i & 1)) {

            if ((j >> i & 1) || i + 2 >= m) return -1;

            o |= 1 << i;

            res++;

            for (int u = i + 1; u <= i + 2; u++) {

                o |= 1 << u;

                if ((q >> u & 1) || !(p >> u & 1) || (k >> u & 1) || (j >> u & 1)) return -1;

            }

            i = i + 2;

        }

        if ((q >> i & 1) && (p >> i & 1) && !(k >> i & 1)) {

            if ((j >> i & 1) || i + 1 >= m) return -1;

            res++;

            o |= 1 << i;

            int u = i + 1;

            o |= 1 << u;

            if (!(q >> u & 1) || !(p >> u & 1) || (k >> u & 1) || (j >> u & 1)) return -1;

            i = i + 1;

        }

    }

    return res;

}

bool judge(int i, int s) {

    if (i < 1) return true;

    return !(s & g[i]);

}

int main() {

    int T; scanf("%d", &T);

    while (T--) {

        cnt = tot = 0;

        memset(g, 0, sizeof g);

        scanf("%d%d%d", &n, &m, &K);

        for (int i = 1, x, y; i <= K; i++) {

            scanf("%d%d", &x, &y); g[x] |= 1 << (y - 1);

        }

        for (int j = 0; j < (1 << m); j++) {

            for (int k = 0; k < (1 << m); k++) {

                if (check(k, j)) s[tot++] = make_pair(j, k);

            }

        }

        for (int i = 0; i < tot; i++) {

            for (int j = 0; j < tot; j++) {

                int res = get(s[i].y, s[i].x, s[j].y, s[j].x);

                if (res != -1) {

                    d[cnt++] = (Node) { j, i, res, o};

                }

            }

        }

        memset(f, 0xcf, sizeof f);

        f[0][0] = 0;

        for (int i = 1; i <= n; i++) {

            for (int j = 0; j < cnt; j++) {

                if (!judge(i - 2, s[d[j].b].y) || !judge(i - 1, s[d[j].b].x) || !judge(i - 1, s[d[j].a].y) || !judge(i, s[d[j].a].x | d[j].y)) continue;

                if (f[i - 1][d[j].b] < 0) continue;

                f[i][d[j].a] = max(f[i][d[j].a], f[i - 1][d[j].b] + d[j].c);

            }

        }

        printf("%d\n", f[n][0]);

    }

}

巴特西

AcWing 328. 芯片（二进制写法）

最新文章

热门文章

巴特西

AcWing 328. 芯片 （二进制写法）

最新文章

热门文章

AcWing 328. 芯片（二进制写法）