传送门: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;
}