题解 P4363 【[九省联考2018]一双木棋chess】

· · 题解

更好的阅读

原题传送门

这道题珂以轮廓线dp解决

经过推导，我们珂以发现下一行的棋子比上一行的棋子少（或等于），而且每一行中的棋子都是从左向右依次排列（从头开始，中间没有空隙）

所以每下完一步棋，棋盘的一部分是有棋子的，另一部分是没棋子的

那么，我们就珂以用一条轮廓线来表示有棋子的部分和没棋子的部分的分界线

我们珂以用一个二进制数表示轮廓线，长n+m位，含有n个1和m个0，轮廓线从右上走到左下，二进制中一位1表示向下1格，0表示向左1格

再经过推导，珂以发现每多下一步棋，轮廓线中的一个1就会向前移一位

有了这些我们就珂以开始设计方程，进行记忆化搜索

我们设L为一条轮廓线，用f[L]表示这个轮廓线距离游戏结束菲菲还能比牛牛多多少分

所以边界条件就是f[((1<<n)-1)<<m]，最终答案便是f[(1<<n)-1]

转移答案时，顺着轮廓线寻找珂以落子的位置，然后根据是谁下的比Min或Max就行了

时间复杂度应该是O(\frac{(n+m)!}{n!m!})

完整代码(代码下方有一些对代码中位运算的解释)

#include <bits/stdc++.h>
#define N 10
#define inf (1<<30)
#define getchar nc
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf; 
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; 
}
inline int read()
{
    register int x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
inline void write(register int x)
{
    if(!x)putchar('0');if(x<0)x=-x,putchar('-');
    static int sta[20];register int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
inline int Max(register int x,register int y)
{
    return x>y?x:y;
}
inline int Min(register int x,register int y)
{
    return x<y?x:y;
}
int n,m;
int a[N][N],b[N][N];
int f[1<<(N<<1)];
bool vis[1<<(N<<1)];
inline int dfs(register int now,register int who)
{
    if(vis[now])
        return f[now];
    f[now]=who?-inf:inf;
    int x=n,y=0;
    for(register int i=0;i<n+m-1;++i)
    {
        if(now>>i&1)
            --x;
        else
            ++y;
        if((now>>i&3)!=1)
            continue;
        int nxt=now^(3<<i);
        if(who)
            f[now]=Max(f[now],dfs(nxt,who^1)+a[x][y]);
        else
            f[now]=Min(f[now],dfs(nxt,who^1)-b[x][y]);
    }
    vis[now]=true;
    return f[now];
}
int main()
{
    n=read(),m=read();
    for(register int i=0;i<n;++i)
        for(register int j=0;j<m;++j)
            a[i][j]=read();
    for(register int i=0;i<n;++i)
        for(register int j=0;j<m;++j)
            b[i][j]=read();
    vis[((1<<n)-1)<<m]=true;
    write(dfs((1<<n)-1,1));
    return 0;
}

关于位运算的解释

1.

    if(now>>i&1)
        --x;
    else
        ++y;

这实际就是扫描轮廓线的过程，先左移i位，使得倒数第i+1位在最后，再与1“&”一下就珂以判断倒数第i+1为是0还是1，从而判断该状态的子状态的位置

2.

    if((now>>i&3)!=1)
         continue;

3的二进制是11，因为只有当状态连续的两位是01（前一位是0，后一位是1）才能转移，这句话就是判断了这个格子是否能下棋子

3.

    int nxt=now^(3<<i);

这句能确定转移后轮廓线的形状，原来的两位是01，异或上11就成了10

·-    ->     |
|           -·