BZOJ-1087: [SCOI2005]互不侵犯King（状压

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1087

先把每行所有的状态DFS出来，然后DP即可。

代码（第一次的状压DP写的很丑。。。）：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
#define MAXN 10
#define MAXM 10010
#define MAXK 100
#define check(x,y) ((!(x&y)))&&(!((x<<1)&y))&&(!((x>>1)&y))
 
int count(int x) {
    int rec=0;
    for (int i=x;i;i>>=1) if (i&1) rec++;
    return rec;
}
 
int n,k,St[MAXM],N=0;
 
void dfs(int x,int y) {
    St[++N]=x;
    if (y>n) return ;
    for (int i=y;i<=n;i++) dfs(x^(1<<(n-i)),i+2);
}
 
long long f[MAXN][MAXM][MAXK];
 
int main() {
    scanf("%d%d",&n,&k);
    dfs(0,1);
    memset(f,0,sizeof(f));
    for (int i=0;i++<N;) if (count(St[i])<=k) f[1][i][count(St[i])]=1;
    for (int i=1;i++<n;) {
        for (int a=0;a++<N;) for (int b=0;b<=k;b++) {
            for (int c=0;c++<N;) {
                if (check(St[a],St[c])&&b>=count(St[a])) {
                    f[i][a][b]+=f[i-1][c][b-count(St[a])];
                }
            }
        }
    }
    long long ans=0;
    for (int i=0;i++<N;) ans+=f[n][i][k];
    printf("%lld\n",ans);
    return 0;
}