为什么会输出一个特别诡异的数啊……求救
查看原帖
为什么会输出一个特别诡异的数啊……求救
52349
张文思楼主2018/5/27 15:35
#include<bits/stdc++.h>
using namespace std;
int n,k;
//int dp[maxn][maxn];
const int maxn=9+5;
long long dp[maxn][maxn*maxn][1000];
int num1(int x)
{
	int cnt=0;
	do
	{
		if(x%2) cnt++;
		x/=2;
	}while(x);
	return cnt;
}
int opt(int i,int j,int k)
{
	if(i==1)
	{
		if((j==num1(k))&&(!(k<<1)&k)) return 1;
		else return 0;
	}
	if(dp[i][j][k]!=-1) return dp[i][j][k];
	long long ans=0;
	int k1=num1(k);
	//cout<<k1<<endl;
	//dp[i][j][k]=sum{dp[i-1][j-?][l]};
	for(int l=0;l<=(1<<n)-1;l++)
	{
		if((l&k)||((l<<1)&k) ||((l>>1)&k)) continue;
		if((l&(l<<1)) || (l&(l>>1))) continue;
		ans+=opt(i-1,j-k1,l);
	}
	return dp[i][j][k]=ans;
}
int main()
{
	memset(dp,-1,sizeof(dp));
	scanf("%d",&n,&k);
	long long haha=opt(n+1,k,0);
	printf("%lld",&haha);
	return 0;
 } 
2018/5/27 15:35
加载中...