[状压] [博弈论dp] P4363 一双木棋

· · 个人记录

这是道博弈论的题，可以用一个带权有向图描述。那么题意其实是已知起始和终止局面，以及每个局面转移到下个局面的权值，让两个人分别走边，每个人的目的是自己的总值比另一个的总值越大越好，假设两人足够聪明，求最终 A 比 B 的总值大多少？

首先是局面的描述，肯定不能暴力做。发现已选格子必定成下三角的形状，刚好有种思想叫轮廓线：提取下三角最外层的线（轮廓），状压表示它，0/1 表示 左/右 走一步。顺着这个我们还能发现总状态至多 C_{n+m}^{n} 种（相当于在每个时刻决定向不向左走）。

然后是比较难搞的博弈论部分。尝试从起始局面顺着推，每次选择最优的，但这样具有后效性，太贪了点。换句话说，由于两人足够聪明，所以贪心得到的结果不一定实现的了，对手也会想到这一点然后阻止你这样做，其实就是可行性问题。

然后有种套路：从后往前推。设局面 S 走到最终局面的结果，保证可以这样由 S 走到最终局面，但完全不考虑此前的可行性。考虑 S 的下一步 s_i，假设是 A 走，那么走到哪里就由 A 说了算，为了最优，一定是选择让对手最劣的走法。

（不理解的话，多想想状态的定义）

仔细想想，这样做的话就恰好在每次转移的时候满足了可行性，使得整个过程满足无后效性（通过状态定义削弱了后效性的影响）。

总结：做博弈论题目时，首先把问题转化为模型，正着推不行时可以考虑倒推。尤其是该题对后效性问题的处理，感觉很有参考性。

代码

对于一个 L 形拐角，可以通过异或 3 * 2^i 来转换到下一状态。建议自己画图试试。

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

#define int long long
const int N = 22, inf = 1145141919810;
int n, m, a[N][N][2], f[1 << N]; 

inline int dfs(int S, int id){
    if(f[S] ^ inf) return f[S];
    for(int i = 0, S2, x = 0, y = m; i < n + m; ++i){
        if((S >> i) & 1) ++x;
        else --y;
        if(y < 0 || x > n || y > m) continue;
        if((!((S >> i) & 1)) && ((S >> i + 1) & 1)){
            S2 = S ^ (3 << i);
            if(!id){//轮到0下 
                dfs(S2, id ^ 1); 
                if(f[S] == inf || f[S2] + a[x + 1][y + 1][0] > f[S])
                    f[S] = f[S2] + a[x + 1][y + 1][0]; 
            }
            else{
                dfs(S2, id ^ 1); 
                if(f[S] == inf || f[S2] - a[x + 1][y + 1][1] < f[S])
                    f[S] = f[S2] - a[x + 1][y + 1][1];          
            }
        }
    }
    return f[S];
}
signed main(){
    for(int i = 0; i < 1 << N; ++i) f[i] = inf;
    cin >> n >> m;
    for(int p = 0; p < 2; ++p)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                scanf("%lld", &a[i][j][p]);
    f[(1 << n) - 1] = 0;
    cout << dfs(((1 << n) - 1) << m, 0);
    return 0;
}
//轮廓线由(0,m)开始