题目描述

blablabla

样例

blablabla

算法1

(3进制状压DP) $O(t \times n * 3^m \times 3^m)$

f[i][j] 表示第$i$行状态为$j$的最多放置数

三进制, 对于每位有 0 1 2 三种状态, 分别代表 (i, j) 线下延申的格数

比如 1, 就是(i, j) 向下延申一格

由于 $3^10$ 较大, 采用滚动数组

且合法拼接上一层的状态较少, 采用dfs dp

时间复杂度

参考文献

C++ 代码

int f[2][59049], p[11];
bool v[N][M];

void dfs(int k, int st, int c, int q, int num) {
    if (q == m) { umax(f[k & 1][c], f[k & 1 ^ 1][st] + num); umax(cas, f[k & 1][c]); return;}
    if (st / p[q] % 3) { dfs(k, st, c + p[q] * (st / p[q] % 3 - 1), q + 1, num); return; }
    if (k < n && q < m-1 && !v[k][q] && !v[k][q + 1] && !v[k + 1][q] && !v[k + 1][q + 1] &&
        !(st/p[q+1]%3)) { //判断(k, p) (k, p + 1) (k + 1, p) (k + 1, p + 1) 四格能不能放
        if (q < m - 2 && !v[k][q + 2] && st / p[q + 2] % 3 == 0 && !v[k + 1][q + 2])
            dfs(k, st, c + p[q] * 13, q + 3, num + 1);
        if (k < n - 1 && !v[k + 2][q] && !v[k + 2][q + 1])
            dfs(k, st, c + p[q] * 8, q + 2, num + 1);
    }
    dfs(k, st, c, q + 1, num);
}

int main() {
    IOS; p[0] = 1; rep(i, 1, 10) p[i] = p[i - 1] * 3; memset(f[1], -1, sizeof f[1]);
    for (cin >> _; _; --_) {
        memset(f[n & 1], -1, sizeof f[0]); f[0][0] = 0; cas = -1;
        cin >> n >> m >> k; memset(v, 0, sizeof v);
        rep(i, 1, k) { int x, y; cin >> x >> y; v[x][--y] = 1; }
        rep(i, 1, n) rep(j, 0, p[m] - 1) if (~f[i & 1 ^ 1][j])
            dfs(i, j, 0, 0, 0), f[i & 1 ^ 1][j] = -1;
        cout << cas << '\n';
    }
    return 0;
}