NOIP专题（一） 状压DP

自学的状压DP
如果有错误欢迎指正
不喜勿喷

• 首先，所谓的状压DP，我认为是一种非常暴力的算法，就是用二进制hash所有的状态，通过记忆化搜索等方式，进行转移
• 其次，要想掌握状压DP，应对位运算这种东东做到熟练的应用。

• 状压dp常见的问题有棋盘问题，覆盖问题，TSP等，一般n<=20都可以考虑它
  一.棋盘问题
  洛谷p1896 [SCOI2005]互不侵犯

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

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

输出格式：
所得的方案数

输入样例#1：
3 2
输出样例#1：
16
思路：我们可以用一个二进制数表示每一行的状态
显然，每一个0，1串需满足以下要求：

• 没有两个相邻的1
• 他的上一行与下一行都不同时为1

• 他左移一位或右移一位满足条件2

  上代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
int n,kk;
int f[15][6222][100]={
  0};//i行，状态j,用了s国王的方案数 
int zh[2005];//这一行放几个国王
int si[60005];//状态 
int cnt=0;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
  if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void dfs(int h,int sum,int wei){
  //干掉条件一 
    if(wei>=n){
        ++cnt;
        si[cnt]=h;
        zh[cnt]=sum;
        return ;
    }
    dfs(h,sum,wei+1);//不放
    dfs(h+(1<<wei),sum+1,wei+2); 
}
main(){
    n=read();
    kk=read();
    dfs(0,0,0);
    for(int i=1;i<=cnt;i++)f[1][i][zh[i]]=1;
    for(int i=2;i<=n;i++)
     for(int j=1;j<=cnt;j++)
      for(int k=1;k<=cnt;k++)
      {
        if(si[j]&si[k]) continue;
        if((si[j]<<1)&si[k]) continue;
        if(si[j]&(si[k]<<1)) continue;
        for(int s=kk;s>=zh[j];s--)f[i][j][s]+=f[i-1][k][s-zh[j]];
      }
      long long ans=0;
      for(int i=1;i<=cnt;i++) ans+=f[n][i][kk];
      printf("%lld",ans);
    return 0;
}