题目描述

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

注：数据有加强（//）

输入输出格式

输入格式：

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

输出格式：

所得的方案数

输入输出样例

输入样例#： 复制

输出样例#： 复制

#include<cstdio>

#include<iostream>

#include<cstring>

#define N 15

#define M 110

#define MAX 550

using namespace std;

/*

见蓝书641页

*/

int s[MAX]; // 记录一行可能的状态

int num[MAX]; //s数组对应每个状态放了多少个猛兽

int states;

long long f[N][M][MAX]; //f[i][j][k]第i行状态为k，放了j个猛兽

int n,m;

void init_state() //预处理s,num数组，代表一行之内所有的可能性

{

    states = ;

    for(int i = ; i < ( << n); i++) //注意，这里是枚举状态

    {

        if(i & (i << )) //处理一排上的冲突情况

            continue;

        int t = i;

        num[states] = ;

        while(t)

        {

            num[states] += (t & );

            t = t >> ;

        }

        s[states++] = i;  //保存状态

    }

}

void dp()

{

    int a,c,mm,b,cc;

    long long ans;

    memset(f,,sizeof(f));

    //单独算第一行和最后一行

    for(int i = ; i < states; i++)

    {

        int j = num[i];

        if(j <= m)  //不能超过总数

            f[][j][i]++;

    }

    for(int i = ; i < n; i++) //2~n - 1行

    {

        for(int j = ; j <= m; j++) // 到第i行，一共放了j个猛兽

        {

            for(a = ; a < states; a++) //i行状态

            {

                c = num[a];

                if(c > j)

                    continue;

                mm = j - c;//前i - 1行的总数

                for(int b = ; b < states; b++) //枚举i-1行

                {

                    cc = num[b];

                    if(cc > mm)

                        continue;

                    if(s[a] & s[b]) //上下有攻击

                        continue;

                    if(s[a] & (s[b] << )) //对角有攻击

                        continue;

                    if(s[b] & s[a] << ) // 同上

                        continue;

                    f[i][j][a] += f[i - ][mm][b];

                }

            }

        }

    }

    ans = ;

    for(a = ; a < states; a++) //最后一行

    {

        c = num[a];

        if(c > m)

            continue;

        int j = m - c;

        for(int b = ; b < states; b++) //枚举n-1行

        {

            cc = num[b];

            if(cc > j)

                continue;

            if(s[a] & s[b]) //上下有攻击

                continue;

            if(s[a] & (s[b] << )) //对角有攻击

                continue;

            if(s[b] & s[a] << ) // 同上

                continue;

            f[n][m][a] += f[n - ][j][b];

        }

        ans += f[n][m][a];

    }

    printf("%lld\n",ans);

}

int main()

{

    scanf("%d%d",&n,&m);

    init_state();

    dp();

    return ;

}

#include<bits/stdc++.h>

using namespace std;

const int M=<<;

long long g[M],h[M],f[][M][],n,k,tot=;

int main()

{

    cin>>n>>k;

    memset(f,,sizeof(f));

    for(int x=; x < (<<n); x++) //第一排单独处理

    {

        if(!(x & (x>>)) && !(x&(x<<)))g[x] = ;//处理g数组,同一排左右不矛盾

        int w = x;

        while(w)

        {

            if(w % )h[x]++;

            w /= ;

        }

        if(g[x])

        f[][x][h[x]] = ;

    }

    for(int x = ; x <= n; x++)

    {

        for(int y = ; y < (<<n); y++)

        {

            if(g[y])

            {

                for(int z = ; z < (<<n); z++)

                {

                    if(g[z] && !(y&z) && !(y & (z>>)) && !(y&(z<<))) //只用考虑该排与上一排

                    {

                        for(int w = ; w + h[z] <= k; w++)

                        f[x][z][w + h[z]] += f[x - ][y][w]; //w枚举总共放的国王的个数

                    }

                }

            }

        }

    }

    for(int y=; y<(<<n); y++)tot+=f[n][y][k];

    cout<<tot;

    return ;

}