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

题目链接

https://www.luogu.org/problemnew/show/P1896

题解

比较经典的状压DP题。

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

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

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

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

设当前行状态为\(x\),上一行状态为\(y\),那么可能会出现如下三种冲突:

  • \(x \& y \neq 0\)(即该行国王的上面已经有国王)
  • \((x<<1) \& y \neq 0\)(即该行国王的左上角已经有国王)
  • \(x \& (y<<1) \neq 0\)(即该行国王的右上角已经有国王)

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

转移方程为:

\(f[i][j][l]= \sum f[i-1][x][l-num1[x]]\)(其中\(x\)代表合法的上一行状态,即没有和当前行冲突)

#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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注