bzoj1087 [SCOI2005][状压DP] 互不侵犯King （状压）

时间：2023-03-08 17:53:16

在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是状态。

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int n,m,all,cnt[];

 long long f[][][];

 bool c1[],c2[][];

 long long ans;

 void pre()

 {

      int s;

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

         if((i&(i>>))==)

         {

             s=;

             for(int x=i;x;x>>=)s+=(x&);

             cnt[i]=s;c1[i]=;

         }

      for(int i=;i<=all;i++)if(c1[i])

         for(int j=;j<=all;j++)if(c1[j])

            if(((i&j)==)&&((i&(j>>))==)&&((j&(i>>))==))

               c2[i][j]=;

 }

 int main()

 {

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

     all=(<<n)-;

     pre();

     for(int i=;i<=all;i++)if(c1[i])f[][cnt[i]][i]=;

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

        for(int k=;k<=all;k++)if(c1[k])

           for(int i=;i<=all;i++)if(c1[i])

              if(c2[k][i])

                 for(int p=cnt[k];p+cnt[i]<=m;p++)

                     f[j+][p+cnt[i]][i]+=f[j][p][k];

     long long ans=;

     for(int i=;i<=all;i++)ans+=f[n][m][i];

     printf("%lld",ans);

 }

相关文章