P4363 一双木棋

一双木棋：合法轮廓上的极大极小搜索

问题

P4363 一双木棋 - 洛谷
两人轮流在 $n\times m$ 的棋盘上放棋子，落子后棋盘仍需满足题目的轮廓限制。先手获得 $A_{i,j}$，后手获得 $B_{i,j}$，双方都采取最优策略，求最终分差。
数据规模：$n, m \le 10$。

这题的数据规模很小，思路大概是状态压缩；考虑直接记录每个格子的情况，发现总状态数是 $\mathcal{O}(2^{nm})$，这个规模就不行了。

于是我们回顾题目限制条件 “一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子”。

也就是说，任意时刻，每一行已经填入的格子一定构成一个前缀，并且各行前缀长度满足：$x_1\ge x_2\ge\cdots\ge x_n$

其中 $x_i$ 表示第 $i$ 行已经填了多少格。于是整个棋盘状态可以压缩为状态 $(x_1,x_2,\dots,x_n)$。

接着考虑转移：下一枚棋子若放在第 $i$ 行，它的位置只能是 $(i,x_i+1)$。这个位置合法当且仅当：$x_i < m$，$i=1$ 或 $x_{i-1} > x_i$。

状态使用 $m+1$ 进制编码：$state=(((x_1)(m+1)+x_2)(m+1)+\cdots)+x_n$。

由于直接状压写起来很麻烦，所以我这里使用记忆化搜索，令 dfs(state) 表示从当前状态出发，在双方最优行动下，后续所有落子产生的“先手得分减后手得分”的最大可能结果。

已经落下的棋子数决定当前轮到谁：偶数枚：先手行动，枚举落子并取最大值；奇数枚：后手行动，枚举落子并取最小值。

▶

P4363

int n, m;
ll a[11][11], b[11][11];
ll x[11];

ll encode( ll x[] ) {
    ll state = 0;
    for( int i = 0; i < n; ++ i ) 
        state = state * ( m + 1 ) + x[i];
    return state;
}

map<ll, ll> memo;

ll dfs( ) {
    ll state = encode( x );
    if( memo.count( state ) ) return memo[state];
    int cnt = 0;
    for( int i = 0; i < n; ++ i ) cnt += x[i];
    if( cnt == n * m ) return memo[state] = 0;

    ll res;
    if( cnt % 2 == 0 ) {
        res = -inf;
        for( int i = 0; i < n; ++ i ) {
            if( x[i] == m ) continue;
            if( i > 0 && x[i] == x[i-1] ) continue;
            int j = x[i];
            x[i] ++;
            res = max( res, a[i][j] + dfs( ) );
            x[i] --;
        }
    } else {
        res = inf;
        for( int i = 0; i < n; ++ i ) {
            if( x[i] == m ) continue;
            if( i > 0 && x[i] == x[i-1] ) continue;
            int j = x[i];
            x[i] ++;
            res = min( res, dfs( ) - b[i][j] );
            x[i] --;
        }
    }
    return memo[state] = res;
}

void solve( ) {
    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( );
        }
    }
    cout << dfs( ) << '\n';
}

---

当然这只是一种做法，另外一种更显然的轮廓线做法是，从左下角开始，一直走到右上角，每次向上走一步记为 0，向右走一步记为 1，于是整个图就可以用这一条轮廓线来表示，状态数为 $\mathcal{O}(2^{n+m})$。

由于每一次落子，其实等价于：

x   x |   x   x |
   --      
x |       x   x |
--        --  --
1 0 1 0   1 1 0 0

也就是把一段 $01$ 变成了 $10$，从初始状态 $000 \dots 0111 \dots 1$ 变成最终状态 $111 \dots 1000 \dots 0$。然后转移同上，也可以实现。

▶

P4363

ll a[11][11], b[11][11];
ll f[1 << 20];
bool vis[1 << 20];
int n, m, len;

ll dfs( int mask, int cnt ) {
    if( cnt == n * m ) return 0;
    if( vis[mask] ) return f[mask];
    vis[mask] = true;

    ll res = cnt & 1 ? inf : -inf;

    int x = n, y = 0;
    for( int pos = 0; pos + 1 < len; ++ pos ) {
        int cbit = ( mask >> pos ) & 1;
        int nbit = ( mask >> ( pos + 1 ) ) & 1;

        if( cbit == 0 && nbit == 1 ) {
            int i = x - 1, j = y;
            int nxt = mask ^ ( 1 << pos ) ^ ( 1 << ( pos + 1 ) );
            if( cnt & 1 ) res = min( res, dfs( nxt, cnt + 1 ) - b[i][j] );
            else res = max( res, a[i][j] + dfs( nxt, cnt + 1 ) );
        }

        if( cbit == 0 ) x --;
        else y ++;
    }

    return f[mask] = res;
}

void solve( ) {
    n = read( ), m = read( );
    len = n + m;

    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( );
        }
    }

    int start = ( ( 1 << m ) - 1 ) << n;
    cout << dfs( start, 0 ) << '\n';
}

不过本题的两种做法，行前缀向量与二进制轮廓线，本质上描述的是同一个合法棋盘状态。前者直接记录每行已经填入的长度，状态转移表现为某一行长度增加 $1$；后者记录填充区域的边界，状态转移表现为相邻的 $01$ 交换为 $10$。

两种表示的合法状态数都为 $\displaystyle \binom{n+m}{n}$，并且一次落子在两种状态之间保持一一对应。因此，两份程序实际上是在同一张有向无环状态图上进行极大极小搜索，只是采用了不同的状态编码。

前者因为序列是单调的，后者因为一共有 $n$ 个 $0$ 和 $m$ 个 $1$。

记录

这题保留为 C 类记录。核心增量是：面对看似为棋盘子集的博弈状态，先利用合法局面的几何结构，把二维集合压缩成一条单调轮廓，再在轮廓状态上做记忆化极大极小搜索。