题解 P4363 【[九省联考2018]一双木棋chess】

· · 题解

作为一名正式选手表示自己这道题考场上被吊打了。。。。

考场上所有的技能就只剩下暴搜了，然后一发\alpha-\beta剪枝混了60分走人

%%%楼下的楼下的楼下。。。的楼下，翻了半天似乎都是哈希做法，那我来一发轮廓线的DP吧

进入正题

首先，由于一个位置能落子，当且仅当上面和左边都没有空位，根据这个依赖关系的传递性，不难发现一个位置能落子，当且仅当左上角的矩形内部也只有自己一个空位。

那么，可以证明，任何时候，棋盘上的棋子都是一个连续且单调的的左上三角形，所有我们可以用一个轮廓线来表示三角形的右下边界，这样就可以表达棋盘的状态了

不妨用 1 表示竖着的轮廓边，0 表示横着的轮廓边。
从左下角开始，任何一个轮廓线都可以表达为长度为 n+m，且拥有n个1，m个0 的01串

比如下图中，初始状态就是 00011

显然第一步棋是唯一的，下完以后的轮廓线可以表示为 00101

如果这个时候走第一行第二列，那么状态可以表示为 01001

如果这个时候走第二行第一列，那么状态可以表示为 00110

然后，可以发现，状态的转移就是把其中一个 1 向左挪一个位置即可

本质就是 01->10

所有找到这些位置就可以转移啦

然后发现转移的顺序不太明显。。。记忆化搜索。。。

令 S 表示一条从左下到右上的轮廓线，令 f[S] 表示这个轮廓线的状态距离游戏结束还能得多少分,可以得到边界条件 f[11\cdots1100\cdots00] = 0，最终的答案便是 f[00\cdots0011\cdots11]

转移的时候看看是谁在下棋，顺着轮廓线定位到当前落子的位置，然后取个 min,max 就好了，代码较短，复杂度是 \binom{n+m}{n} 的，所以跑的比较快。

#include <bits/stdc++.h>
using namespace std;

inline int read(int u = 0, char c = getchar(), bool f = false) {
    for (;!isdigit(c); c = getchar()) f |= c == '-';
    for (; isdigit(c); c = getchar()) u = (u << 1) + (u << 3) + c - '0';
    return f ? -u : u;
}

const int maxn = 10;
const int oo = 1e9 + 7;

int a[maxn][maxn], b[maxn][maxn];

int f[1 << (maxn << 1)];

int dfs(int sta, bool who, int n, int m) {
    if (~f[sta]) return f[sta];
    f[sta] = who ? -oo : oo;
    int x = n, y = 0;
    for (int i = 0; i < n + m - 1; i++) {
        if (sta >> i & 1) x--; else y++;
        if ((sta >> i & 3) != 1) continue;
        int nxt = sta ^ (3 << i);
        if (who) 
            f[sta] = max(f[sta], dfs(nxt, who ^ 1, n, m) + a[x][y]);
        else    
            f[sta] = min(f[sta], dfs(nxt, who ^ 1, n, m) - b[x][y]);
    }   
    return f[sta];  

}

int main() {
    int n = read(), m = read(); 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            a[i][j] = read();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            b[i][j] = read();
    memset(f, 0xff, sizeof(f));
    f[((1 << n) - 1) << m] = 0;
    cout << dfs((1 << n) - 1, 1, n, m) << endl;
}

UPD:

妈呀代码出锅了。。。拿 -1 表示没有搜索过似乎是错的。。。不管啦。。。数据水。。。就过了。。。 心疼考场使用 next 而 CE 的同学们。。。