求助!80分
查看原帖
求助!80分
442474
LanXingXuan楼主2021/1/24 16:02
#include<bits/stdc++.h>
using namespace std;
int dp[10][1000][100];
int gs[1000];
bool checkh(int x)
{
	if(x&(x<<1))return false;
	else return true;
}
bool checkl(int x1,int x2)
{
	if(x1&x2)return false;
	if(x1&(x2>>1))return false;
	if(x1&(x2<<1))return false;
	return true;
}
void initgs()
{
	int num,x;
	for(int i=0;i<=512;i++){
		num=0;
		x=i;
		for(int j=0;j<9;j++){
			if(x&1) num++;
			x>>=1;
		} 
		gs[i]=num;
	}
}
int main()
{
	int N,K;
	int ans=0;
	initgs();
	memset(dp,0,sizeof dp);
	cin>>N>>K;
	for(int j=0;j<(1<<N);j++){
		if(checkh(j)){
			dp[1][j][gs[j]]=1;
		}
	}
	for(int i=2;i<=N;i++){
		for(int j=0;j<(1<<N);j++){
			if(!checkh(j)) continue;
			for(int k=gs[j];k<=K;k++){
				for(int t=0;t<(1<<N);t++){
					if(!checkh(t))continue;
					if(!checkl(t,j))continue;
					dp[i][j][k]+=dp[i-1][t][k-gs[j]];
				}
			}
		}
	}
	for(int i=0;i<=(1<<N);i++){
		ans+=dp[N][i][K];
	}
	cout<<ans;
} 
2021/1/24 16:02
加载中...