【bzoj1087】互不侵犯King

Description

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

Input

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

Output

　　方案数。

Sample Input

　　3 2

Sample Output

Solution

我们很容易的联想到状态压缩动态规划

f[i][j][k][S]表示当前做到(i,j)这个格子共放了k个国王红色部分状态为S的方案数

然后只要枚举当前格子放不放的问题了

红色部分使用状态压缩，而红色部分之前的东西已经不影响答案了

当然可以使用滚动数组

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<string>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<queue>

#include<map>

#include<vector>

#include<set>

#define il inline

#define re register

using namespace std;

typedef long long ll;

int s=,t=,n,m;

ll f[][][],ans=;

il bool chk(int j,int S){

     if(j==n) return (S&)==&&(S&)==&&(S&(<<n))==;

     else if(j==) return (S&)==&&(S&)==;

     return (S&)==&&(S&)==&&(S&(<<n))==&&(S&)==;

}

int main(){

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

    if(n==){

        cout<<"";exit();

    }

    if(n==){

        if(m==) cout<<"";

        else if(m==) cout<<"";

        else cout<<"";

        exit();

    }

    f[][][]=;

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

        for(int j=;j<=n;j++){

            memset(f[t],false,sizeof(f[t]));

            for(int S=;S<(<<n+);S++){

                for(int l=;l<=m;l++){

                    if(chk(j,S)) f[t][l+][(S>>)|(<<n)]+=f[s][l][S];

                    f[t][l][S>>]+=f[s][l][S];

                }

            }

            swap(s,t);

        }

    }

    for(int S=;S<(<<n+);S++) ans+=f[s][m][S];

    cout<<ans;

    return ;

}

秒客网