想问一下此题状压的做法 是不是做不了啊
查看原帖
想问一下此题状压的做法 是不是做不了啊
247269
MSqwq楼主2021/6/3 23:41
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

ll n,m;
ll cnt,tot;
ll f[110][1<<15];
bool v[1<<15];

int main()
{
	while(1)
	{
		scanf("%lld%lld",&n,&m);
		memset(v,0,sizeof(v));
		memset(f,0,sizeof(f));
		tot=(1<<n)-1;
		for(int i=0;i<=tot;i++)
		{
			v[i]=1;
			cnt=0;
			for(int j=0;j<n;j++)
			{
				if((i>>j)&1)
				{
					if(cnt&1)v[i]=0;
					cnt=0;
				}
				else cnt++;			
			}
			if(cnt&1)v[i]=0;
		}
		
		f[0][0]=1;
		for(int i=1;i<=m;i++)
		{
			for(int j=0;j<=tot;j++)
			{
				for(int k=0;k<=tot;k++)
					if((j&k)==0&&v[j|k])f[i][j]+=f[(i-1)][k];	
			}
		}
		printf("%lld\n",f[m][0]);		
	}
}
2021/6/3 23:41
加载中...