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

原题传送门

这道题珂以轮廓线dp解决

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

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

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

(1)格

(1)就会向前移一位

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

(f[L])表示这个轮廓线距离游戏结束菲菲还能比牛牛多多少分

(f[(1<<n)-1])

(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;

(1)，从而判断该状态的子状态的位置

2.

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

(1)）才能转移，这句话就是判断了这个格子是否能下棋子

3.

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

(10)

·-    ->     |
|           -·