题目链接：P1896 互不侵犯
分析：普通的状压DP再多加一维记个数，然后找到能转移到当前的状态更新答案；
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=(1<<10)+7; ll dp[15][maxn][110]; int num[maxn]; bool tag[maxn]; int main() { int n,m;scanf("%d%d",&n,&m); for (int i=0;i<(1<<n);i++) { if(((i<<1)&i)==0) tag[i]=true; int x=i; while(x) {if(x&1)num[i]++; x>>=1;} if(tag[i] && num[i]<=m) dp[1][i][num[i]]=1; } for (int i=2;i<=n;i++) for (int j=0;j<(1<<n);j++) { if(!tag[j]) continue; for (int k=0;k<(1<<n);k++) { if(!tag[k]) continue; if((k&j)==0 && ((k>>1)&j)==0 && ((k<<1)&j)==0) for(int l=num[j];l<=m;l++) dp[i][j][l]+=dp[i-1][k][l-num[j]]; } } ll ans=0; for(int i=0;i<(1<<n);i++) ans+=dp[n][i][m]; printf("%lld\n",ans); return 0; }
