<洛谷P1896互不侵犯>（状态压缩DP）

题目描述

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

输入输出格式

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

输出格式： 所得的方案数

输入输出样例

输入样例#1： 3 2 输出样例#1： 16

作为第一道状压DP题，它教会了我如何看懂一段看不懂的代码——使劲看 @ · @ （滑稽那么什么是状压DP呢？本蒟蒻的理解是用二进制数模拟不同的状态。举个栗子：某个东西所放置的位置记为1，空着的位置记为0。比如1000101表示从右往左第1,3,7位有东西，其余空着。然后利用位运算来巧妙地实现不同状态之间的转移和判断。这道题的意思是：每个点的周围8个位置都不能有其他点，询问方案数。可以先思考，如果没有K个国王的限制，应该怎么做。因为每一行的可行的状态都一样，那么首先可以预处理出每一种状态，即求出任意一行的所有不冲突的状态（用二进制存储），然后一行一行遍历，只需要这一行不与上一行冲突即可。若是加入K个国王的条件，只需要多加一个判断条件：国王总数不超过K。预处理的方法（每一行的状态一样，只需处理一次）： 1. 从0开始，枚举每一个位置放或不放，若放则记为1，否则为0。如枚举到5时，二进制数为101，则代表第1,3个位置放国王 2. 用位运算判断是否符合条件 if(i&(i<<1)) continue;

即若某个数左移一位后与原数取交结果不为0，那么这个数不满足“左右没有其他国王”的条件。 3. 用一个数组存状态，另一个存每个状态中的国王的数量。

DP转移方程：f[i][j][a]+=f[i-1][m][b]; 表示第i行，共放了j个国王，状态为a时的方案数。

又是喜闻乐见的代码

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,k; int st; int s[550],num[550]; long long f[15][110][550]; long long ans=0; void init_state(); void DP(); int main(){ scanf("%d%d",&n,&k); init_state(); DP(); return 0; } void init_state(){//预处理任意一行的状态 st=0; for(int i=0;i<(1<<n);++i){ if(i&(i<<1)) continue; int t=i; num[st]=0; while(t){ num[st]+=(t&1);//存数量 t=t>>1; } s[st++]=i;//存状态 } return; } void DP(){ ans=0; memset(f,0,sizeof(f)); for(int i=0;i<st;++i){//预处理第一行 int j=num[i]; if(j<=k) f[1][j][i]++; } for(int i=2;i<n;++i)///枚举行数 for(int j=0;j<=k;++j)//枚举国王个数 for(int a=0;a<st;++a){//枚举本行状态 int c=num[a]; if(c>j) continue; int m=j-c; for(int b=0;b<st;++b){//枚举上一行状态 int cc=num[b]; if(cc>m) continue; if(s[a]&s[b]) continue; if(s[a]&(s[b]<<1)) continue; if((s[a]<<1)&s[b]) continue;//与上一行不冲突 f[i][j][a]+=f[i-1][m][b]; } } ans=0; for(int a=0;a<st;++a){//枚举最后一行，应该可以和其它行合并在一起DP，不过没试过 int c=num[a]; if(c>k) continue; int j=k-c; for(int b=0;b<st;++b){ int cc=num[b]; if(cc>j) continue; if(s[a]&s[b]) continue; if(s[a]&(s[b]<<1)) continue; if((s[a]<<1)&s[b]) continue; f[n][k][a]+=f[n-1][j][b]; } ans+=f[n][k][a]; } printf("%lld",ans); return; }