首页 > 代码库 > 互不侵犯King(bzoj 1087)

互不侵犯King(bzoj 1087)

Description

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

Input

  只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)

Output

  方案数。

Sample Input

3 2

Sample Output

16
/*
  一看就是状压DP,而且状态也很好设,dp[i][j][s]表示前i行填了j个国王,第i行的状态是s的方案数。
  但是这样直接转移,状态太多,会超时,我们发现,由于不能攻击到相邻的,所以每一行的状态是不多的,可以预处理一下。 
*/
#include<cstdio>
#include<iostream>
#define M 600
#define lon long long
using namespace std;
lon dp[10][100][M];
int map[M][M],stay[M],num[M],m,n,k;
void dfs(int s,int last,int t){
    stay[++m]=s;
    num[m]=t;
    if(t>=k) return;
    for(int i=last+2;i<=n;i++)
        dfs(s+(1<<i-1),i,t+1);
}
int main(){
    scanf("%d%d",&n,&k);
    dfs(0,-1,0);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            if(stay[i]&stay[j]||((stay[i]<<1)&stay[j])||((stay[i]>>1)&stay[j]))
                map[i][j]=1;
    dp[0][0][1]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
            for(int s1=1;s1<=m;s1++){
                if(num[s1]>j) continue;
                for(int s2=1;s2<=m;s2++)
                    if(!map[s1][s2]&&num[s1]+num[s2]<=j)
                        dp[i][j][s1]+=dp[i-1][j-num[s1]][s2];
            }
    lon ans=0;
    for(int i=1;i<=m;i++) ans+=dp[n][k][i];
    printf("%lld",ans);
    return 0;
}

 

互不侵犯King(bzoj 1087)