「题解」「九省联考 2018」一双木棋 chess

一道简单的 轮廓线 DP + 对抗搜索 入门题。

题目链接:Luogu P4363/BZOJ 5248/LibreOJ 2471/九省联考 2018 D1T1。

题目

题目描述

菲菲和牛牛在一块 $n$ 行 $m$ 列的棋盘上下棋,菲菲执黑棋先手,牛牛执白棋后手。

棋局开始时,棋盘上没有任何棋子,两人轮流在格子上落子,直到填满棋盘时结束。落子的规则是:一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。

棋盘的每个格子上,都写有两个非负整数,从上到下第 $i$ 行中从左到右第 $j$ 列的格子上的两个整数记作 $A _ {i,j}$、$B _ {i,j}$。在游戏结束后,菲菲和牛牛会分别计算自己的得分:菲菲的得分是所有有黑棋的格子上的 $A _ {i,j}$ 之和,牛牛的得分是所有有白棋的格子上的 $B _ {i,j}$ 的和。

菲菲和牛牛都希望,自己的得分减去对方的得分得到的结果最大。现在他们想知道,在给定的棋盘上,如果双方都采用最优策略且知道对方会采用最优策略,那么,最终的结果如何。

数据范围

变量数据范围
$n,m$$\leq 10$
$A_{i,j},B_{i,j}$$\leq 10^5$

时空限制

题目编号时间限制空间限制
Luogu P4363$1\text{s}$$500\text{MiB}$
BZOJ 5248$20\text{s}$$512\text{MiB}$
LibreOJ 2471$1\text{s}$$512\text{MiB}$
九省联考 2018 D1T1$1\text{s}$$512\text{MiB}$

题解

思路

一看到数据范围这么小,就想到状态压缩的动态规划,但是怎么设状态呢?

显然,无论下棋,轮廓线的长度不变,所以把轮廓设为状态即可,用记忆化搜索提高效率。

代码

时间复杂度为 $\binom{n+m}{n}$。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F //正无穷
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=10; //数据范围

int n,m;
int a[MAXN][MAXN],b[MAXN][MAXN];
int f[1<<(MAXN<<1)]; // dp 数组

inline int DFS(reg int S,reg bool flag){ //对抗搜索,flag 表示当前是谁下棋
    if(f[S]!=-1) //记忆化搜索
        return f[S];
    f[S]=flag?-INF:INF; //初始复赋值
    reg int x=n,y=0;
    for(reg int i=0;i<n+m-1;++i){
        if((S>>i)&1)
            --x;
        else
            ++y;
        if(((S>>i)&3)!=1)
            continue;
        reg int to=(S^(3<<i));
        if(flag)
            f[S]=max(f[S],DFS(to,false)+a[x][y]);
        else
            f[S]=min(f[S],DFS(to,true)-b[x][y]);
    }
    return f[S];
}

int main(void){
    n=read(),m=read();
    for(reg int i=0;i<n;++i)
        for(reg int j=0;j<m;++j)
            a[i][j]=read();
    for(reg int i=0;i<n;++i)
        for(reg int j=0;j<m;++j)
            b[i][j]=read();
    memset(f,-1,sizeof(f)); //记忆化初值为 -1
    f[((1<<n)-1)<<m]=0; //临界状态
    printf("%d\n",DFS((1<<n)-1,true)); //开始求解
    return 0;
}