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
",tot);
return 0;
}
这里打表打的就是(10)个([0,10])整数单调不降的方案数。
运行结果：
184756
既然状态数这么少就直接(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
",dfs(0));return 0;
}