Luogu P1896 [SCOI2005]互不侵犯 题解

#include<bits/stdc++.h>
#define int long long //10年OI一场空，不开long long见祖宗
using namespace std;
int n,K,f[11][1<<10][100],S[1<<10],sum[1<<10],cnt,ans;
signed main(){
cin>>n>>K;
for(int i=0;i<(1<<n);i++){
if(i&(i<<1)) continue ;
S[++cnt]=i;
for(int j=0;j<n;j++)
if((1<<j)&i) sum[cnt]++;
}
f[0][1][0]=1;//初始化
for(int i=1;i<=n;i++){
for(int j=1;j<=cnt;j++){
for(int k=0;k<=K;k++){
if(k<sum[j]) continue ;
for(int p=1;p<=cnt;p++){
if(S[p]&S[j]S[p]&(S[j]<<1)(S[p]<<1)&S[j]) continue ;//是否干扰
f[i][j][k]+=f[i-1][p][k-sum[j]];//DP
}
}
}
}
for(int i=1;i<=cnt;i++) ans+=f[n][i][K];//最终答案求和
cout<<ans<<endl;
}