King

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=492

King

时间限制：3000 ms  |  内存限制：65535 KB

难度：5

描述

在n*n的棋盘上放k个国王(可攻击相邻的8个格子)，求使它们无法互相攻击的方案数。

输入

多组测试数据。
输入包含n和k（0<n<=10,0<k<=n^2）

输出

输出方案数，每组测试数据占一行。

样例输入

2 1
3 2

样例输出

4
16

思路：我们需要考虑该行各个炮兵之间的布置情况，和上一行的的情况，该行的情况只需要考虑不相邻就可以，上一行通过将本行左移和右移，以及本行的情况和上一行按位与==0才可以。所以我们需要一个s数组记录每行可以排列的情况，c数组代表该种情况有几个1，因为国王的个数有限制，这里要特别注意的是输出要用cout 具体原因不清楚，用%I64d就会WA，之后还要注意dp数组要开成long long 型的

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int s[1<<11];///用二进制数来记录一行的多种部署
long long dp[12][1<<11][150];///第i行,状态为s[j]，且前i行已经放置了t个棋子的方案数
int c[1<<11];///和S同步记录该行该种方案放了多少个棋子
int num=0;
int n,k;

int Cnt(int s)//当前状态有多少个1
{
    int cnt = 0;
    while (s > 0)
    {
        cnt++;
        s &= (s-1);
    }
    return cnt;
}

//枚举各种状态
void init()
{
    num = 0;
    for (int i=0; i<(1<<n); i++)
        if ( !(i & i<<1) )
        {
            s[++num] = i;
            c[num] = Cnt(i);
        }
}
int main()
{
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        memset(s,0,sizeof(s));
        memset(c,0,sizeof(c));
        init();
        for(int i=1;i<=num;i++)
            if(k>=c[i])
            dp[1][i][c[i]]=1;

        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<=num;j++)
            {
                if(c[j]>k)continue;
                for(int m=1;m<=num;m++)
                {
                    if((s[j]&s[m])||((s[j]<<1)&s[m])||((s[j]>>1)&s[m]))continue;
                    for(int t=0;t<=k;t++)
                    if(t>=c[j])
                        dp[i][j][t]+=dp[i-1][m][t-c[j]];
                }
            }
        }
        long long ans=0;
        for(int i=1;i<=num;i++)
        {
            ans+=dp[n][i][k];
        }
       cout<<ans<<endl;;
    }
    return 0;
}