萌新求助(玄关)
查看原帖
萌新求助(玄关)
1287433
__ycy1124__楼主2024/7/17 17:07
#include<bits/stdc++.h>
using namespace std;
long long dp[10][100][5000];
int val[5000],w[5000];
int js=0;
int n,k;
void dfs(int p,int m,int q){
	if(p==n||p==n+1){
		val[++js]=m;
		w[js]=q;
		return;
	}
	dfs(p+1,m,q);
	dfs(p+2,m+1,q+(p<<1));
}
int main(){
	scanf("%d%d",&n,&k);
	dfs(0,0,0);
	//for(int i=1;i<=js;i++){
	//	printf("%d ",w[i]);
	//}
	for(int i=1;i<=js;i++){dp[1][val[i]][i]=1;}
	for(int i=2;i<=n;i++){
		for(int j=1;j<=js;j++){
			for(int ii=1;ii<=js;ii++){
				if(w[j]&w[ii]){continue;}
				else if((w[j]>>1)&w[ii]){continue;}
				else if((1<<w[j])&w[ii]){continue;}
				for(int jj=k;jj>=val[j]+val[ii];jj--){dp[i][jj][j]+=dp[i-1][jj-val[j]][ii];}
			}
		}
	}
	long long ans=0;
	for(int i=1;i<=js;i++){ans+=dp[n][k][i];}
	printf("%lld",ans);
	return 0;
}
2024/7/17 17:07
加载中...