若只代码求调悬棺
查看原帖
若只代码求调悬棺
697189
00ll00楼主2024/3/25 17:39
#include<bits/stdc++.h>
using namespace std;
struct node{
	int a,b;
}a[114514];
int n,k,cnt;
long long dp[10][100][1145];
//void tox(int n,int o){
//	if(o==-1)return;
//	cout<<(n&(1<<o))?1:0;
//	tox(n,o-1);
//}
int main(){
	cin>>n>>k;
	for(int i=1;i<(1<<(n));i++){
		int qwq=0;
		if((i&((i<<1)|(i>>1)))==0){
			int w=i;
			while(w){
				w-=(w&(-w));
				qwq++;
			}
			a[++cnt].a=i;
			a[cnt].b=qwq;
//			tox(i,k);
//			cout<<" "<<i<<"\n";
		}
	}
	dp[0][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int l=1;l<=cnt;l++){
			node q=a[l];
			for(int r=1;r<=cnt;r++){
				node p=a[r];
				if(((q.a)|(q.a>>1)|(q.a<<1))&p.a) {
					for(int j=q.b;j<=k;j++){
						dp[i][j][q.a]+=dp[i-1][j-q.b][p.a];
					}
				}
			
			}
		} 
	}
	int ans=0;
	for(int i=1;i<=cnt;i++){
		ans+=dp[n][k][a[cnt].a];
	}cout<<ans;
	return 0;
}
2024/3/25 17:39
加载中...