萌新求助!调了好久,样例都没过!
查看原帖
萌新求助!调了好久,样例都没过!
383601
shijihong楼主2022/6/23 13:05
#include<bits/stdc++.h>
using namespace std;
int dp[12][84][1024];
int num[1024];
int getsum(int x){
	int tot=0;
	while(x>0){
		tot+=x&1;
		x<<=1; 
	}
	return tot;
}
int main(){
	int n,p;
	cin>>n>>p;
	for(int i=0;i<(1<<n);i++) num[i]=getsum(i);
	for(int i=0;i<(1<<n);i++) if((i&(i<<1))==0) dp[1][num[i]][i]=1;
	for(int i=2;i<=n;i++){
		for(int j=0;j<(1<<n);j++){
			for(int sum=0;sum+num[j]<=n*n;sum++) 
				for(int k=0;k<(1<<n);k++)
					if(!(j&(j<<1)) and !(k&(k<<1)) and !(j&k) and !(j&(k<<1)) and !(k&(j<<1)))
						dp[i][sum+num[j]][j]+=dp[i-1][sum][k];
		}
	}
	int ans=0;
	for(int i=0;i<(1<<n);i++) ans+=dp[n][p][i];
	cout<<ans<<endl;
	return 0;
}


2022/6/23 13:05
加载中...