sol

首先，要保证一个格子的左边和上方都放满了棋子，就需要这个点的左上方那个矩形都放满了棋子。

这样放棋子状态就会是一个自左下至右上的轮廓线。

状态数？\(C_{20}^{10}\)。相当于是从左下角走到右上角一共要走\(20\)步，在其中选出\(10\)向上走其余的向右走。

也可以打个表看一看。。。

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m,a[20],tot;

void dfs(int u)

{

	if (u==n+1) {++tot;return;}

	for (int i=a[u-1];i<=m;++i)

		a[u]=i,dfs(u+1);

}

int main()

{

	n=10;m=10;dfs(1);

	printf("%d\n",tot);

	return 0;

}

这里打表打的就是\(10\)个\([0,10]\)整数单调不降的方案数。

运行结果：

既然状态数这么少就直接\(hash\)一下然后\(map\)存啊。

把既然是\([0,10]\)的整数就把它压成一个\(11\)进制的数，显然并不会爆long long。

可以直接\(dp\)。判断一下当前状态是先手还是后手进行操作，如果是先手操作就是从所有后继状态的\(dp\)值中取\(\max\)，否则就是取\(\min\)。

code

#include<cstdio>

#include<algorithm>

#include<map>

using namespace std;

#define ll long long

int gi()

{

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 20;

const int inf = 2e9;

int n,m,A[N][N],B[N][N],a[N];

map<ll,int>M;

ll hash()

{

	ll res=0;

	for (int i=1;i<=n;++i) res=res*11+a[i];

	return res;

}

void unpack(ll zt)

{

	for (int i=n;i;--i) a[i]=zt%11,zt/=11;

}

int dfs(ll zt)

{

	if (M.find(zt)!=M.end()) return M[zt];

	unpack(zt);int t=0,res;

	for (int i=1;i<=n;++i) t^=a[i]&1;

	res=t?inf:-inf;

	for (int i=1;i<=n;++i)

		if (a[i-1]>a[i])

		{

			++a[i];

			ll nxt=hash();

			if (t) res=min(res,dfs(nxt)-B[i][a[i]]);

			else res=max(res,dfs(nxt)+A[i][a[i]]);

			--a[i];

		}

	return M[zt]=res;

}

int main()

{

	n=gi();m=gi();a[0]=m;

	for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) A[i][j]=gi();

	for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) B[i][j]=gi();

	for (int i=1;i<=n;++i) a[i]=m;M[hash()]=0;

	printf("%d\n",dfs(0));return 0;

}

巴特西

[BZOJ5248][多省联测2018]双木棋chess

sol

code

最新文章

热门文章