bzoj1087: [SCOI2005]互不侵犯King

1087: [SCOI2005]互不侵犯King

Description

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

Input

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

Output

　　方案数。

Sample Input

3 2

Sample Output

16 感觉自己特别不会做这一类型的题，开始看到的时候有一点点思路，应该是要状态压缩，但是发现并不会写……经过学习，大概懂了一点套路，也决定来写个博客。 首先想到用二进制来表示每一行进行状压，于是dp[i][j][p]就表示到第i行共用j个棋子，并且第i行的状态为p又几种方案。很容易知道，两个棋子是不能相邻的，所以先预处理出没有棋子相邻的所有状态。然后动规，枚举行数，棋子个数，此行的状态，上一行的状态，判断后相加。最后将枚举每一种状态i，sigmadp[n][k][i]就是答案。 代码就这样QAQ #include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; int n,k; long long res=0; long long f[10][100][700],pd[1000],num[1000]; int main() { cin>>n>>k; for (int i=0;i<(1<<n);i++) { if (!(i&(i<<1)))//没有两个相邻 { pd[i]=1; int ls=i; while (ls) { num[i]+=(ls&1); ls=ls>>1; } f[1][num[i]][i]=1; } } for (int i=2;i<=n;i++) { for (int j=0;j<=k;j++) { for (int nw=0;nw<(1<<n);nw++) { if (!pd[nw]) continue; if (num[nw]>k) continue; for (int la=0;la<(1<<n);la++) { if (!pd[la]) continue; if (num[la]>k||la&nw||la&(nw<<1)||(la<<1)&nw) continue;//三种不可行的状态 f[i][j][nw]+=f[i-1][j-num[nw]][la]; } } } } for (int i=0;i<(1<<n);i++) { res+=f[n][k][i]; } printf("%lld",res); }