求助,90分!
查看原帖
求助,90分!
157147
ljh6jz楼主2020/9/18 19:53
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 11,M=600;
int n,k;
ll ans;
ll dp[N][M][N];
int s[M],num[M],l;

ll read(){
	ll k=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		k=k*10+ch-'0';
		ch=getchar();
	}
	return w*k;
}

void print(){
	for(int j=1;j<=n;++j){
		for(int i=1;i<=l;++i){
			printf("%d ",dp[j][i][k]);
		}
		printf("\n");
	}
}

void pre(){
	for(int i=0;i<(1<<n);++i){
		if(i&(i<<1))continue;
		s[++l]=i;
		for(int j=0;j<n;j++){
			if(i&(1<<j))num[l]++;
		}
	}
}

void dp_work(){
	dp[0][1][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=l;++j){
			for(int p=0;p<=k;++p){
				if(p>=num[j]){
					for(int t=1;t<=l;t++){
						if((s[j]&s[t])>0||((s[j]<<1)&s[t])>0||((s[j]>>1)&s[t])>0){
							continue;
						}
						dp[i][j][p]+=dp[i-1][t][p-num[j]];
					}
				}
			}
		}
	}
	for(int i=1;i<=l;++i){
		ans+=dp[n][i][k];
	}
}

int main(){
	cin>>n>>k;
	pre();
	dp_work();
	cout<<ans;
	return 0;
}
2020/9/18 19:53
加载中...