洛谷P1896 [SCOI2005]互不侵犯King

时间：2023-03-09 09:16:45
洛谷P1896 [SCOI2005]互不侵犯King

P1896 [SCOI2005]互不侵犯King

题目描述

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

输入输出格式

输入格式：

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

输出格式：

所得的方案数

输入输出样例

输入样例#1： 复制 
3 2
输出样例#1： 复制 
16
#include<iostream>

#include<cstdio>

using namespace std;

int n,k,top=;

int c[<<],s[<<];

long long f[][<<][];

void dfs(int cond,int sum,int pos){

    if(pos>n){

        c[++top]=cond;

        s[top]=sum;

        return;

    }

    dfs(cond+(<<pos-),sum+,pos+);

    dfs(cond,sum,pos+);

}

int main(){

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

    dfs(,,);//处理出一行的所有状态

    for(int i=;i<=top;i++)f[][c[i]][s[i]]=;

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

        for(int j=;j<=top;j++)//一共有top种状态

            for(int h=;h<=top;h++){

                if(c[j]&c[h])continue;

                if((c[j]<<)&c[h])continue;

                if((c[j]>>)&c[h])continue;

                for(int sum=k;sum>=s[j];sum--)

                f[i][c[j]][sum]+=f[i-][c[h]][sum-s[j]];

            }

    long long ans=;

    for(int i=;i<=top;i++)ans+=f[n][c[i]][k];

    cout<<ans;

    return ;

}

相关文章