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

[SCOI2005]互不侵犯 解题报告

题目描述

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

输入输出格式

输入格式：

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

输出格式：

所得的方案数

输入输出样例:

input

3 2

output

16

思路：

N的个数是十分小的 (即使这样爆搜也会T飞！！)

所以用一波 状压DP！

设f[i][j][k]代表前i行放了k个，排列方式是j,(j的二进制形式就是排列方式)。

可以 (必须) 先预处理出一行的可行排列情况：

void dfs(int w,int sum,int num)//分别为排列情况，放的点的个数，到底几个点了{
    	if(num>=n)	{
    		sit[++cnt]=w;		gs[cnt]=sum;		return;	}	dfs(w,sum,num+1);//不防这个点	dfs(w+(1<

那么根据题意，这个方案与另一个方案是否冲突 就显而易见啦

sit[j]&sit[k]==1 上下相邻 (sit[j]<<1)&sit[k]==1 斜着相邻 sit[j]&(sit[k]<<1) ==1 同上

DP+判断 code：

第一行：到第几行了

第二行：这一行的的排列情况 第三行：这一行的的排列情况可以从上一行的哪几个状态转移过来。

for(int i=2;i<=n;i++)		for(int j=1;j<=cnt;j++)			for(int k=1;k<=cnt;k++)			{
    				if(sit[j]&sit[k])continue;				if((sit[j]<<1)&sit[k]) continue;				if(sit[j]&(sit[k]<<1)) continue;				for(int s=K;s>=gs[j];s--) f[i][j][s]+=f[i-1][k][s-gs[j]];			}

完整代码：

#include
   
    using namespace std;#define maxn 2005int cnt,n,K;int sit[maxn],gs[maxn];long long f[10][maxn][105];long long ans;void dfs(int w,int sum,int num){
    	if(num>=n)	{
    		sit[++cnt]=w;		gs[cnt]=sum;		return;	}	dfs(w,sum,num+1);	dfs(w+(1<
    
     =gs[j];s--) f[i][j][s]+=f[i-1][k][s-gs[j]];			}	ans=0;	for(int i=1;i<=cnt;i++) ans+=f[n][i][K];	printf("%lld",ans);	return 0;}
    
   

注意开long long。。。

转载地址：http://yyuci.baihongyu.com/