样例过不去求助
查看原帖
样例过不去求助
190931
cannotdp楼主2023/4/14 07:16

调了一整个早上了,马上要回班上早读了,求助

#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;

const int N=1e5+10,M=1e4+10,O=1e3+10,mod=1e9+7,INF=0x3f3f3f3f;
int n,m,t,q,ans,cnt,num,tot,k;
string s;
int p[2050],ik[2050],f[10][110][2010];

signed main() {
	scanf("%lld%lld",&n,&k);
	for(int i=0;i<(1<<n);i++) {
		int t=i;
		while(t) {
			if(t&1) p[i]++;
			t>>=1;
		}
		if((i&(i<<1))||(i&(i>>1))) continue;
		ik[++num]=i;
	}
	f[0][0][0]=1;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=num;j++) {
			int v1=ik[j];
			for(int k=1;k<=num;k++) {
				int v2=ik[k];
				if((v1&v2)||((v1>>1)&v2)||((v1<<1)&v2)) continue;
				for(int u=p[v1];u<=k;u++) f[i][u][v1]+=f[i-1][u-p[v1]][v2];
			}
		}
	}
	for(int i=1;i<=num;i++) ans+=f[n][k][ik[i]];
	printf("%lld",ans);
	return 0;
}

2023/4/14 07:16
加载中...