题目分析

题意理解

这是一个特殊的棋盘游戏：

• 棋盘大小：n × m
• 落子规则：一个格子可以落子当且仅当它的左侧和上方所有格子都有棋子
• 这意味着棋子只能从左上角开始，逐步填充到右下角
• 菲菲（先手）得分：所有黑棋格子的 A[i][j] 之和
• 牛牛（后手）得分：所有白棋格子的 B[i][j] 之和
• 双方都采用最优策略，求菲菲得分 - 牛牛得分

关键观察

1. 落子顺序固定：由于落子规则，棋子的填充顺序实际上是从左上到右下的对角线顺序
2. 状态表示：可以用一个长度為 n+m-1 的二进制数表示当前棋盘状态
   • 1 表示向下的移动
   • 0 表示向右的移动
3. 轮廓线DP：这是典型的轮廓线动态规划问题

算法思路

状态设计

使用一个 n+m 位的二进制数表示当前状态：

• 前 n 位为 1，后 m 位为 0 表示初始状态（空棋盘）
• 1 表示"向下"的边界，0 表示"向右"的边界
• 状态转移：找到 "01" 模式，翻转为 "10"

博弈DP

• dp[state] 表示在状态 state 下，当前玩家能获得的最大分数差（从当前玩家视角）
• 菲菲最大化：dp[state] = max(下一状态 + A[x][y])
• 牛牛最小化：dp[state] = min(下一状态 - B[x][y])

代码详解

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

const int INF = 1 << 30;
int n, m;
int A[15][15], B[15][15];
int dp[1 << 20];      // 记忆化数组
bool vis[1 << 20];    // 访问标记

// DFS搜索：now-当前状态, who-当前玩家(1:菲菲, 0:牛牛)
int dfs(int now, int who) {
    if (vis[now]) return dp[now];  // 记忆化
    
    // 初始化当前状态的值
    dp[now] = who ? -INF : INF;    // 菲菲求最大，牛牛求最小
    
    int x = n, y = 0;  // 当前坐标 (从虚拟的左上角开始)
    
    // 遍历状态的所有位，寻找可以落子的位置
    for (int i = 0; i < n + m - 1; ++i) {
        // 更新当前坐标：1表示向下，0表示向右
        (now >> i & 1) ? --x : ++y;
        
        // 检查是否可以落子：需要找到"01"模式
        // "01"表示可以从当前格子向右下角移动
        if ((now >> i & 3) != 1) continue;
        
        // 计算下一个状态：将"01"翻转为"10"
        int nxt = (now ^ (3 << i));
        
        // 根据当前玩家进行状态转移
        if (who) 
            // 菲菲的回合：最大化自己的优势
            dp[now] = max(dp[now], dfs(nxt, who ^ 1) + A[x][y]);
        else 
            // 牛牛的回合：最小化菲菲的优势（即最大化自己的优势）
            dp[now] = min(dp[now], dfs(nxt, who ^ 1) - B[x][y]);
    }
    
    vis[now] = true;
    return dp[now];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    
    // 读入A矩阵（菲菲的得分）
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> A[i][j];
    
    // 读入B矩阵（牛牛的得分）        
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> B[i][j];
    
    // 初始化终态：所有格子都被填充
    // 状态表示：前n位为1，后m位为0
    // 例如：n=2,m=3时，初始状态为 11100
    vis[((1 << n) - 1) << m] = true;
    dp[((1 << n) - 1) << m] = 0;
    
    // 从初始状态开始搜索：棋盘为空，菲菲先手
    cout << dfs((1 << n) - 1, 1) << endl;
    
    return 0;
}

算法核心要点详解

1. 状态表示技巧

对于 n×m 的棋盘，使用长度为 n+m 的二进制串：

• 初始状态：111...100...0（n个1，m个0）
• 最终状态：000...011...1（n个0，m个1）
• 状态意义：1表示向下边界，0表示向右边界

2. 坐标计算

在状态遍历时维护当前坐标 (x,y)：

(now >> i & 1) ? --x : ++y;

• 遇到1：y坐标不变，x坐标-1（向下移动）
• 遇到0：x坐标不变，y坐标+1（向右移动）

3. 合法移动检测

寻找模式 "01"：

• "01" 表示当前有一个向下的边界接一个向右的边界
• 这对应着一个可以落子的格子
• 翻转为 "10" 表示在该格子落子

4. 博弈策略

• 菲菲（先手）：希望最大化 自己的得分 - 对手的得分
• 牛牛（后手）：希望最小化 菲菲的得分 - 自己的得分，即最大化 自己的得分 - 菲菲的得分

因此转移方程为：

• 菲菲：dp[state] = max(下一状态 + A[x][y])
• 牛牛：dp[state] = min(下一状态 - B[x][y])

5. 复杂度分析

• 状态数：C(n+m, n) 种状态，n,m≤10 时最多 C(20,10)=184756 种状态
• 每个状态：最多 O(n+m) 次转移
• 总复杂度：可以接受

示例演示

以样例 n=2, m=3 为例：

初始状态：11000 （2个1，3个0）

状态转移过程：

1. 找到第一个"01"在位置1：1[01]000 → 翻转为 1[10]000
2. 对应落子在 (1,1)，菲菲得分 +A[1][1]
3. 继续递归...

总结

这道题的核心技巧：

1. 轮廓线状态压缩：用二进制串表示棋盘填充状态
2. 博弈DP：交替进行最大化/最小化搜索
3. 记忆化搜索：避免重复计算
4. 坐标映射：从状态位推算出实际棋盘坐标

这是一个经典的博弈论+状态压缩DP问题，很好地考察了对状态设计和博弈策略的理解。