学长说这是模板题…… 貌似确实是…… 算了QAQ 因为数组的原因让DQS帮我调了半天……QAQ果然dp不爽系列
;const int MAXN = 1 << 11;long long dp[12][MAXN][100];int n,king;int get_k(int x){int ans = 0;for(int i = n;i >= 1;i –)if(x & (1 << i))ans ++;return ans;}void print(int x){for(int i = n;i >= 1;i –)cout<<( (x >> i) & 1);cout<<” “;}bool cannot(int x){return (x & (x << 1)) && (x & (x >> 1));}void dpdpd(){for(int i = 0;i < (1 << (n + 1));i ++)dp[1][i][get_k(i)] = 1;for(int i = 2;i <= n;i ++){for(int l = 0;l < (1 << (n + 1));l ++){if(cannot(l)) continue;for(int j = 0;j < (1 << (n + 1));j ++){int us = get_k(j);if(cannot(j)) continue;if(!(l & 1) && !(j & 1) && !(j & l) && !(j & (l << 1)) && !(j & (l >> 1))){for(int k = 0;k <= king – us;k ++){dp[i][j][k + us] += dp[i – 1][l][k];// print(l);print(j);printf(“%d %d %d %d\n”,i,dp[i-1][l][k],dp[i][j][k+us],k+us);puts(“”);}}}}}return;}int main(){scanf(“%d %d”,&n,&king);dpdpd();long long ans = 0;for(int i = 0;i < (1 << (n + 1));i ++)ans += dp[n][i][king];printf(“%lld\n”,ans);return 0;}
，想念我的时候，不要忘记我也在想念你。
