玄2关0分wa求调
查看原帖
玄2关0分wa求调
768270
__why楼主2024/12/22 10:59
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
int sum,tmp;
int dp[12][90][2005];
int cnt[2005];
int zt[2005];
signed main(){
	dp[0][0][0] = 1;
	cin>>n>>k;
	cnt[0] = 0;
	cnt[1] = 1;
	for(int i = 2;i<(1<<n);i++){
		cnt[i] = cnt[i>>1]+(i%2?1:0);
		if((i&(i<<1))||(i&(i>>1)))continue;
		zt[++tmp] = i;
	}
	for(int i = 1;i<=n;i++){
		for(int tt = 1,kz;tt<=tmp;tt++){
			kz = zt[tt];
			for(int j = cnt[kz];j<=k;j++){
				for(int _ = 1,kk;_<=tmp;_++){
					kk = zt[_];
					if(cnt[kk]+cnt[kz]>j)continue;
					if(((kk>>1)&kz)||((kk<<1)&kz))continue;
					dp[i][j][kz] += dp[i-1][j-cnt[kz]][kk];
				}
			}
		}
	}
	for(int i = 1;i<=tmp;i++){
		sum+=dp[n][k][zt[i]];
	}
	cout<<sum;
}
2024/12/22 10:59
加载中...