车II

Time Limit:1000MS Memory Limit:65536K

Description

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

Input

n , m , k n,m,k n,m,k

Output

方案总数

Sample Input

3 3 2

Sample Output

24

分析：

n ∗ m < = 80 n*m<=80 n∗m<=80 状压 D P DP DP解决
数组 s u m sum sum保存一行中所有的 n u m num num的放置方案 则 s u m sum sum数组可以在预处理过程中用 d f s dfs dfs求出
同时用 c i ci ci保存第 i i i个状态中 1 1 1的个数 可以借此避免重复计算
f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示第 i i i行的状态为 s u m [ j ] sum[j] sum[j]且前i行放 k k k个棋子的方案数
方程：
f [ i ] [ s u m [ j ] ] [ p ] + = f [ i − 1 ] [ s u m [ l ] ] [ p − c [ j ] ] ; f[i][sum[j]][p]+=f[i-1][sum[l]][p-c[j]]; f[i][sum[j]][p]+=f[i−1][sum[l]][p−c[j]];
最后做一个累加 得到最终的答案

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,k,num,ans;
int f[105][1024][31],c[2048],sum[2048];
void dfs(int res,int dep,int flag)
{
	if(dep>n)
	{
		sum[++num]=res;
		c[num]=flag;  //放置方案
		return;
	}
	dfs(res,dep+1,flag);
	dfs(res|(1<<dep-1),dep+2,flag+1);
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	if(n>m) swap(n,m);
	dfs(0,1,0);
	for(int i=1;i<=num;i++)
		f[1][sum[i]][c[i]]=1;
	for(int i=2;i<=m;i++)
		for(int j=1;j<=num;j++)
			for(int l=1;l<=num;l++)
				if(!(sum[j]&sum[l]))
					for(int p=0;p<=k;p++)
						if(p>=c[j])
							f[i][sum[j]][p]+=f[i-1][sum[l]][p-c[j]];  //状压DP
	for(int i=1;i<=num;i++)
		ans+=f[m][sum[i]][k];  //累加最终ans
	printf("%d",ans);
	return 0;
}