[BZOJ 5248][九省联考 2018] 一双木棋【轮廓线DP+对抗搜索】
Problem:
Description
菲菲和牛牛在一块n行m列的棋盘上下棋，菲菲执黑棋先手，牛牛执白棋后手。棋局开始时，棋盘上没有任何棋子，两人轮流在格子上落子，直到填满棋盘时结束。落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。棋盘的每个格子上，都写有两个非负整数，从上到下第i行中从左到右第j列的格子上的两个整数记作Aij、Bij。在游戏结束后，菲菲和牛牛会分别计算自己的得分：菲菲的得分是所有有黑棋的格子上的Aij之和，牛牛的得分是所有有白棋的格子上的Bij的和。菲菲和牛牛都希望，自己的得分减去对方的得分得到的结果最大。现在他们想知道，在给定的棋盘上，如果双方都采用最优策略且知道对方会采用最优策略，那么，最终的结果如何。
Input
第一行包含两个正整数n,m，保证n,m≤10。接下来n行，每行m个非负整数，按从上到下从左到右的顺序描述每个格子上的第一个非负整数：其中第i行中第j个数表示Aij。接下来n行，每行m个非负整数，按从上到下从左到右的顺序描述每个格子上的第二个非负整数：其中第i行中第j个数表示Bij
n, m ≤ 10 ， Aij, Bij ≤ 100000
Output
输出一个整数，表示菲菲的得分减去牛牛的得分的结果。
Sample Input
2 3 2 7 3 9 1 2 3 7 2 2 3 1
Sample Output
2
HINT
Source
Solution:
这是一道神奇的轮廓线 DP 题。所谓轮廓线 DP，就是一类以当前已取部分和未取部分的轮廓线为状态的状压 DP。
在这道题中，我们假定左下角为起始点，轮廓线延伸的方向只能向右或向上。
记向右延伸为 0，向上延伸为 1，则轮廓线可以描述为一个长为 n + m 的二进制串。那么
- 初始状态可表示为 11...100...0 (n 个 1, m 个 0) = 2n + m - 2m
- 终止状态可表示为 00...011...1 (m 个 0, n 个 1) = 2n - 1。
考虑 DP 的状态转移方程，令 f[S][1] 为轮廓线状态为 S 时，选取轮廓线以下部分所能得到的最大收益，f[S][0] 则表示同样条件下所能得到的最小收益，nxtS 表示 S 的后继状态，x, y 为该后继状态与 S 相比少选取的点的坐标。则不难得到
- f[S][1] = max{f[nxtS][0]} + A[x][y]
- f[S][0] = min{f[nxtS][1]} - B[x][y]
通过记忆化搜索可以较方便地求解上式。这种一方最大化答案，另一方最小化答案的搜索被称为对抗搜索。
最后的问题是如何求解后继状态。
通过观察可知，只有连续两位为 "10" 处是合法的选取位置，而选择后轮廓线会转化为 "01"。
枚举每一位检查是否符合条件，并进行转移即可。
显然，该算法的时间复杂度为 O(状态数)，而由于只能向右或向上走的限制，状态二进制串中的 0 和 1 个数保持不变，所以最多有 C(n + m, n) ≤ 184756 种不同状态，可以通过。
Code: O(状态数) [9480K, 420MS]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
inline void getint(int &num){
int ch; bool neg = 0;
while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
num = ch & 15;
while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
if(neg) num = -num;
}
inline void checkmax(int &a, const int &b) {if(b > a) a = b;}
inline void checkmin(int &a, const int &b) {if(b < a) a = b;}
int n, m, A[12][12], B[12][12], f[1 << 20][2]; // 轮廓线: 1 表示向上, 0 表示向右
int maxex, sumB = 0;
int dfs(int S, bool flag){ // 返回轮廓线 S 以下部分的最大或最小值 (取决于 flag)
if(f[S][flag] < INF) return f[S][flag];
int x = n + 1, y = 0, res = flag ? 0xc0c0c0c0 : 0x3f3f3f3f;
for(register int ex = maxex - 1; ~ex; ex--)
if(S & (1 << ex)) x--;
else{
y++;
if(S & (1 << ex + 1)){
int nxtS = S ^ (1 << ex) ^ (1 << ex + 1);
if(flag) checkmax(res, dfs(nxtS, !flag) + A[x][y]);
else checkmin(res, dfs(nxtS, !flag) - B[x][y]);
}
}
return f[S][flag] = res;
}
int main(){
getint(n), getint(m);
for(register int i = 1; i <= n; i++)
for(register int j = 1; j <= m; j++) getint(A[i][j]);
for(register int i = 1; i <= n; i++)
for(register int j = 1; j <= m; j++) getint(B[i][j]);
memset(f, INF, sizeof(f)), f[(1 << n) - 1][0] = f[(1 << n) - 1][1] = 0;
maxex = n + m, printf("%d\n", dfs((1 << n + m) - (1 << m), 1));
return 0;
}
发表评论