萌新刚学OI,0pts求调
查看原帖
萌新刚学OI,0pts求调
922691
Hisy楼主2024/7/16 21:01
#include<bits/stdc++.h>
#define MAXN 2002
using namespace std;
typedef long long ll;
int cnt[MAXN],chk[MAXN];
ll dp[11][101][MAXN];
int main(){
	int n,k,top=0;
	scanf("%d %d",&n,&k);
	for(int i=0;i<(1<<n);++i){
		int x=i,sum=0;
		while(x){
			if(x&1){
				++sum;
			}
			x>>=1;
		}
		cnt[n]=sum;
		if((((i<<1)|(i>>1))&i)==0){
			chk[++top]=i;
		}
	}
	dp[0][0][0]=1ll;
	for(int i=1;i<=n;++i){
		for(int l=1;l<=top;++l){
			for(int r=1;r<=top;++r){
				int x=chk[l],y=chk[r];
				if(((y|(y<<1)|(y>>1))&x)==0){
					for(int j=0;j<=k;++j){
						if(j-cnt[x]>=0){
							dp[i][j][x]+=dp[i-1][j-cnt[x]][y];
						}
					}
				}
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=top;++i){
		ans+=dp[n][k][chk[i]];
	}
	printf("%lld",ans);
	return 0;
}
2024/7/16 21:01
加载中...