状压DP
f[i][j][k]表示当前在第i行，包括第i行一共放了j个国王，而且这一行状态为k的方案数
那么f[i][j][k]=Sigma(f[i-1][j-cnt[l]][l],其中l为一种可行方案且不和k状态冲突)
然后搞个ans加一下就没了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,K,cnt[1<<10],f[15][105][1<<10],rule[1<<10],ed,ans;
int Cnt(int s){
int ans=0;
while(s){
ans+=s&1;
s>>=1;
}
return ans;
}
int CheckNot(int s,int l){
return (s&l)||(s&(l>>1))||(s&(l<<1));
}
int CheckGood(int s){
int flg=0;
while(s){
if(s&1 && flg)return 0;
flg=s&1;
s>>=1;
}
return 1;
}
void Get(){
for(int i=0;i<=ed;i++){cnt[i]=Cnt(i);rule[i]=CheckGood(i);}
}
int main(){
freopen("1087.in","r",stdin);
freopen("1087.out","w",stdout);
scanf("%lld %lld",&n,&K);
ed=(1<<n)-1;
Get();
for(int i=0;i<=ed;i++)if(rule[i])f[1][cnt[i]][i]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<=ed;j++){
if(!rule[j])continue;
for(int k=0;k<=ed;k++){
if(!rule[k] || CheckNot(j,k))continue;
for(int l=cnt[k];l+cnt[j]<=K;l++)f[i][l+cnt[j]][j]+=f[i-1][l][k];
}
}
}
for(int i=0;i<=ed;i++)ans+=f[n][K][i];
printf("%lld\n",ans);
return 0;
}
评论 (0)
