[洛谷 1896][SCOI2005]互不侵犯

题目链接

https://www.luogu.org/problem/P1896

题解

比较经典的状压 DP 题。

用 \(f(i,j,l)\) 表示处理到第 \(i\) 行，当前行状态为 \(j\)，且已经放置 \(l\) 个国王时的方案数。

其中 \(j\) 的含义是：把 \(j\) 转换为二进制数后，对应位为 \(0\) 代表该列不放国王，否则放国王。

首先 DFS 预处理出一行的所有合法状态以及每个状态部署的国王数，接下来枚举该行的可能状态进行转移。

同行内的冲突在 DFS 预处理的时候已经排除了，接下来考虑处理每一行与上一行的冲突：

• 该行国王的上面已经有国王；
• 该行国王的左上角已经有国王；
• 该行国王的右上角已经有国王。

转移的时候这几种情况需要及时排除。

#include <iostream>
#include <algorithm>
using namespace std;
long long sta[2005],sit[2005],f[15][2005][105];
int n,k,cnt;
void dfs(int x,int num,int cur)
{
 if(cur>=n)
 {
  sit[++cnt]=x;
  sta[cnt]=num;
  return;
 }
 dfs(x,num,cur+1);
 dfs(x+(1<<cur),num+1,cur+2);
}
int main()
{
 cin>>n>>k;
 dfs(0,0,0);
 for(int i=1;i<=cnt;i++)
  f[1][i][sta[i]]=1;
 for(int i=2;i<=n;i++)
  for(int j=1;j<=cnt;j++)
   for(int l=1;l<=cnt;l++)
   {
    if(sit[j]&sit[l])continue;
    if((sit[j]<<1)&sit[l])continue;
    if(sit[j]&(sit[l]<<1))continue;
    for(int p=sta[j];p<=k;p++)
     f[i][j][p]+=f[i-1][l][p-sta[j]];
   }
 long long ans=0;
 for(int i=1;i<=cnt;i++)
  ans+=f[n][i][k];
 cout<<ans<<endl;
 return 0;
}