状压DP-SCOI2005互不侵犯

还是先上题洛谷1896

例题

题目描述

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

输入输出格式

输入格式： 只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N） 输出格式： 所得的方案数

解析

首先这题和cornfield这题类似。 观察发现cornfield求得是四个方向不得相邻，而互不侵犯求得是八个方向不得相邻，并且还要计算国王的数量。所以在cornfield的基础上，还要做一些改进。

改进一：如何判断左上和右上不相邻？ 101 010 将010整体向左移一位。 101 100 第一列的国王相邻。 或将010整体向右移一位 101 001 第三列的国王相邻。 通过运用<<和>>实现。

改进二：如何实现国王数量统计？ 这就不得不使我们将二维数组扩大到三维数组： 设dp[i][j][k]表示当第i行取j状态且已使用k个国王的方案数。 由cornfields那题我们可以轻易得到状态转移方程为 dp[i][j][k]+=dp[i-1][j’][k’] 其中k`的取值范围是i和i-1行状态所用国王数量一直到K。 废话不说，上代码：

代码

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; int n,K,top,tot,t[1000]; long long state[1000],cnt[1000],dp[10][1000][90],ans; bool check(int j,int k)//判断函数 { if(state[j]&state[k])return 0; if((state[j]<<1)&state[k])return 0; if((state[j]>>1)&state[k])return 0; return 1; } void init() { tot=(1<<n); for(int i=0;i<tot;i++) if(!(i&(i>>1)))state[++top]=i; } int main() { scanf("%d%d",&n,&K); init(); cnt[1]=1; for(int i=2;i<tot;i++) cnt[i]=cnt[i>>1]+(i&1); dp[0][0][0]=1; for(int i=1;i<=top;i++) dp[1][i][cnt[state[i]]]=1; for(int i=1;i<=n;i++) for(int j=1;j<=top;j++) for(int k=1;k<=top;k++) if(check(j,k)==1) for(int l=cnt[state[j]]+cnt[state[k]];l<=K;l++) dp[i][j][l]+=dp[i-1][k][l-cnt[state[j]]]; //状态转移方程 for(int i=1;i<=top;i++)ans+=dp[n][i][K]; cout<<ans<<endl; return 0; }