bzoj1087 [SCOI2005][状压DP] 互不侵犯King (状压)

时间:2022-12-17 17:57:45

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

Input

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

Output

  方案数。

Sample Input

3 2

Sample Output

16

 

题解:这题,就是处理两行,首先确定两行都是合法的,

然后枚举上下两行的转移,就可以了,和炮兵阵地差不多。

当然,要确定出,当前这一行的数量,要保证都取了。

所以要三维,前n行,m个King,q是状态。

 

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,m,all,cnt[512];
 5 long long f[10][100][512];
 6 bool c1[512],c2[512][512];
 7 long long ans;
 8 void pre()
 9 {
10      int s;
11      for(int i=0;i<=all;i++)
12         if((i&(i>>1))==0)
13         {
14             s=0;
15             for(int x=i;x;x>>=1)s+=(x&1);
16             cnt[i]=s;c1[i]=1;
17         }
18      for(int i=0;i<=all;i++)if(c1[i])
19         for(int j=0;j<=all;j++)if(c1[j])
20            if(((i&j)==0)&&((i&(j>>1))==0)&&((j&(i>>1))==0))
21               c2[i][j]=1;
22 }
23 int main()
24 {
25     scanf("%d%d",&n,&m);
26     all=(1<<n)-1;
27     pre();
28     for(int i=0;i<=all;i++)if(c1[i])f[1][cnt[i]][i]=1;
29     for(int j=1;j<n;j++)
30        for(int k=0;k<=all;k++)if(c1[k])
31           for(int i=0;i<=all;i++)if(c1[i])
32              if(c2[k][i])
33                 for(int p=cnt[k];p+cnt[i]<=m;p++)
34                     f[j+1][p+cnt[i]][i]+=f[j][p][k];
35     long long ans=0;
36     for(int i=0;i<=all;i++)ans+=f[n][m][i];
37     printf("%lld",ans);
38 }