状态压缩DP具体可参考周伟的《状态压缩》。
状态方程可列为dp[i][s]=dp[i-1][s']+dp[i-1][s] (sum[s]+1<=i)
或者dp[i][s]=dp[i-1][s'] sum[s]==i
其中i表示第几行 s表示状态 s'表示s的子状态
#include<cstdio> #include<iostream> #include<string.h> using namespace std; const int maxn=1<<11; int state[maxn],sum[maxn]; int dp[11][maxn]; int main() { //freopen("test.txt","r",stdin); int n,m; while(~scanf("%d%d",&n,&m)) { int i,j,num=0,k; memset(state,0,sizeof(state)); memset(sum,0,sizeof(sum)); memset(dp,0,sizeof(dp)); for(i=0;i<(1<<n);i++) { k=i; while(k) { sum[num]+=1&k; k>>=1; } state[num++]=i; } for(i=0;i<num;i++) { if(sum[i]>1) continue; dp[0][i]=1; } int r; for(r=1;r<n;r++) { for(i=0;i<num;i++) { if(sum[i]>(r+1)) continue; for(j=0;j<n;j++) { if(i&(1<<j)) { k=1<<j; k=i-k; dp[r][i]+=dp[r-1][k]; } } if(sum[i]==(r+1)) continue; dp[r][i]+=dp[r-1][i]; } } int ans=0; for(i=0;i<num;i++) { if(sum[i]==m) { ans+=dp[n-1][i]; } } printf("%d\n",ans); } return 0; }