why 20point
查看原帖
why 20point
490978
小超手123楼主2022/9/24 22:45
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int dp[10][2<<10][100]; //dp[i][j][k]表示只考虑前i行,第i行状态是j,一共放置k个
int get1(int x) { //求一个状态有多少个1
	int num=0;
	while(x) {
		num++;
		x-=(x&-x);
	}
	return num;
}
bool check(int i,int j){
	if(i&(i<<1))return 1;
	if(j&(j<<1))return 1;
	if(i&&j)return 1;
	if(i&(j<<1))return 1;
	if(i&(j>>1))return 1;
	return 0;
}
int main() {
	cin>>n>>m;
	dp[0][0][0]=1;
	for(int i=1; i<=n; i++) {
		for(int j=0; j<(2<<n); j++) {
			for(int k=0; k<=m; k++) {
				int cnt1=get1(j);
				if(cnt1>k)continue; 
				for(int last=0; last<(2<<n); last++) {
					int cnt2=get1(last);
					if(cnt1+cnt2>k)continue;
					if(!check(j,last))dp[i][j][m]+=dp[i-1][last][k-cnt1];
				}
			}
		}
	}
	for(int i=0;i<(2<<n);i++)ans+=dp[n][i][m];
	cout<<ans;
	return 0;
}
2022/9/24 22:45
加载中...