本文共 741 字，大约阅读时间需要 2 分钟。

车II

Description

有一个nm的棋盘(n、m≤80,nm≤80)要在棋盘上放k(k≤20)个棋子，使得任意两个棋子不相邻。求合法的方案总数。

Input

n,m,k

Output

方案总数

Sample Input

3 3 2

Sample Output

24

解题思路

我们用 DFS 枚举每一种情况，然后枚举冲突，动态转移即可

#include
   
    #include
    
     using namespace std;int n,m,k,s[10010],tot,c[10010],f[82][1<<9][21];void dfs(int ss,int p,int l){   	if(p>n)	{   		s[++tot]=ss;		c[tot]=l;		return;	}	dfs(ss,p+1,l);	dfs(ss+(1<
     
      >n>>m>>k;	if(n>m)		swap(n,m);	dfs(0,1,0);	for(int i=1;i<=tot;i++)		f[1][s[i]][c[i]]=1;	for(int i=2;i<=m;i++)		for(int j=1;j<=tot;j++)			for(int l=1;l<=tot;l++)				if(!(s[j]&s[l]))					for(int o=0;o<=k;o++)						if(o>=c[j])							f[i][s[j]][o]+=f[i-1][s[l]][o-c[j]];	long long ans=0;	for(int i=1;i<=tot;i++)		ans+=f[m][s[i]][k];	cout<
      
       <