【BZOJ】【P1087】【SCOI2005】【互不侵犯King】【状压DP】【题解】

时间:2022-12-17 17:52:58

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1087

蒟蒻好久没写题解了&好久没刷DP了,蒟蒻DP真是烂到爆

首先这个题不能爆搜(显然)于是要DP ==

f[i][j][k] 表示第i行及前i行,第i行状态为j的时候放k个king的方案数

首先预处理合法的一行状态和合法状态的king数,由题意得1是不能相邻的, 所以x&(x<<1) 不能为零就像这样:  x  = 01100  x<<1 = 11000   x&(x<<1) =01000

同理x&(x>>1)也一样,

然后处理合法的两行状态,x y 是上下层且合法当且仅当  x&y  x&(y<<1)  x&(y>>1)  均为0

之后就可以dp了

依次枚举行、合法方案、放置国王数、下层方案,推

DP式:

f[i+1][下层状态][枚举的King数] += f[i][当前状态][当前King数] 

边界f[0][1][0]=1

最后ans=sum(f[n][i][m])  i 属于{ 0 to (1<<n)-1 }

Code:

/*
ID:zky
OJ:BZOJ
Index:1087
Language:C++
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
lld f[11][1<<11][82];
int n,m;
bool ok[1010][1010];
int canopt[1010];
int optsum[1010];
int cnt(int x){
int s=0;
while(x){
if(x&1)s+=1;
x>>=1;
}
return s;
}
bool check1(int x){
if(x&(x<<1))return false;
if(x&(x>>1))return false;
return true;
}
bool check2(int x,int y){
if(x&y)return false;
if(x&(y<<1))return false;
if(x&(y>>1))return false;
return true;
}
int main(){
cin>>n>>m;
for(int i=0;i<(1<<n);i++){
if(check1(i)){
canopt[++canopt[0]]=i;
optsum[++optsum[0]]=cnt(i);
}
}
for(int i=1;i<=canopt[0];i++)
for(int j=i;j<=canopt[0];j++){
if(check2(canopt[i],canopt[j]))
ok[i][j]=ok[j][i]=true;
}
f[0][1][0]=1;
for(int i=0;i<n;i++)
for(int j=1;j<=canopt[0];j++)
for(int k=0;k<=m;k++)
if(f[i][j][k]){
for(int p=1;p<=canopt[0];p++){
if(ok[j][p]&&k+optsum[p]<=m){
f[i+1][p][k+optsum[p]]+=f[i][j][k];
}
}
}
lld ans=0;
for(int i=0;i<(1<<n);i++){
ans+=f[n][i][m];
}
cout<<ans<<endl;
return 0;
}