[SCOI2005]互不侵犯

题目大意：
　　给你一个n*n的棋盘，让你往上面放国王，让它们不会互相攻击。
　　问有几种方案？

思路：
　　状压DP。
　　类似于BZOJ1725，不过现在没有要求哪里一定不能放，但是斜着也不能相邻了。
　　用f[i][j][k]表示第i行状态为j，总共放了k个国王。
　　转移的时候枚举行数i，当前行状态j，上一行状态l，上一行总共放的棋子数k。
　　判断是否合法并转移即可。
　　显然这题打表也可以做，然而DP还是能成功地跑到0ms，在洛谷上是最快的非打表程序。

 1 #include<cstdio>
 2 #include<cctype>
 3 #include<cstring>
 4 typedef long long int64;
 5 inline int getint() {
 6     register char ch;
 7     while(!isdigit(ch=getchar()));
 8     register int x=ch^'0';
 9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
10     return x;
11 }
12 const int N=9,K=26;
13 int64 f[2][1<<N][K];
14 int main() {
15     int n=getint(),k=getint();
16     if(k>((n+1)>>1)*((n+1)>>1)) puts("0");
17     f[0][0][0]=1;
18     for(register int i=1;i<=n;i++) {
19         memset(f[i&1],0,sizeof f[0]);
20         for(register int j=0;j<(1<<n);j++) {
21             for(register int k=1;k<n;k++) {
22                 if((j>>k)&(j>>(k-1))) goto Next_j;
23             }
24             for(register int l=0;l<(1<<n);l++) {
25                 for(register int k=1;k<n;k++) {
26                     if((l>>k)&(l>>(k-1))) goto Next_l;
27                 }
28                 if((j&l)||((j>>1)&l)||((j<<1)&l)) continue;
29                 for(register int k=__builtin_popcount(l);k<=((n+1)>>1)*((n+1)>>1);k++) {
30                     if(!f[!(i&1)][l][k]) continue;
31                     f[i&1][j][__builtin_popcount(j)+k]+=f[!(i&1)][l][k];
32                 }
33                 Next_l:;
34             }
35             Next_j:;
36         }
37     }
38     int64 ans=0;
39     for(register int j=0;j<(1<<n);j++) {
40         ans+=f[n&1][j][k];
41     }
42     printf("%lld
",ans);
43     return 0;
44 }