Description

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

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

　　方案数。
Sample Input
3 2
Sample Output
16
解题思路：
BZOJ上比较水的一个题目了，首先考虑一下搜索是肯定行不通的，因为状态实在是太多了，注意n的大小最多为8，我们可以考虑一下是否可以预处理排除一些状态，然后状压DP,这个实际上就是炮兵阵地的一个翻版了。我们dp[i][j][k] i代表行,j代表当前放了j个马,当前行状态为now，然后枚举转移即可。由于预处理了有效状态，所以DP的转移近乎于（1）的。具体细节在代码中都标注出来了，无坑点！

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define uep(i, a, b) for(int i = a; i < b; i++)
const int maxn = 1<< 9;
int n, m, mask, cnt[maxn];
LL dp[10][100][maxn]; //dp[i][j][k] i代表行,j代表当前放了j个马,当前行状态为now
int f1[maxn], f2[maxn][maxn];
void pre_init(){
    rep(i, 0, mask){
        if((i&(i >> 1)) == 0){
            f1[i] = 1;
            cnt[i] = __builtin_popcount(i);
        }
    }
    rep(i, 0, mask){
        if(f1[i]){
            rep(j, 0, mask){
                if(f2[j]){
                    if(((i&j) == 0) && ((i&(j>>1)) == 0) && ((j & (i>>1)) == 0)){
                        f2[i][j] = 1;
                    }
                }
            }
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    mask = (1 << n) - 1;
    pre_init();
    //初始化第一行DP值
    rep(i, 0, mask) if(f1[i]) dp[1][cnt[i]][i] = 1;
    for(int row = 1; row < n; row ++){
        for(int prestate = 0; prestate <= mask; prestate++){
            if(f1[prestate]){
                for(int curstate = 0; curstate <= mask; curstate++){
                    if(f1[curstate]){
                        if(f2[prestate][curstate]){
                            for(int num = cnt[prestate]; num + cnt[curstate] <= m; num++){
                                dp[row + 1][num + cnt[curstate]][curstate] += dp[row][num][prestate];
                            }
                        }
                    }
                }
            }
        }
    }
    LL ans = 0;
    rep(i, 0, mask){
        ans = ans + dp[n][m][i];
    }
    cout << ans << endl;
    return 0;
}