状压dp70求助
查看原帖
状压dp70求助
394167
Cure_Wing楼主2022/10/6 13:05
/*
	Name: P1896 [SCOI2005] 互不侵犯
	Copyright: Dragon_Horse
	Author: 
	Date: 05/10/22 22:09
	Description: 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
using std::cin;using std::cout;
constexpr int N=10;
int n,w;
long long f[N][1<<N][N],ans;
inline int t(int x){
	int cnt=0;
	for(int i=x;i;i>>=1) cnt+=i&1;
	return cnt;
} 
signed main(){
// 	freopen(".in","r",stdin);
// 	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>w;
	for(int i=0;i<(1<<n);++i)
		if(((i<<1)&i)==0&&((i>>1)&i)==0)
			f[1][i][t(i)]=1;
	for(int i=2;i<=n;++i)
		for(int j=0;j<(1<<n);++j)
			if(((j<<1)&j)==0&&((j>>1)&j)==0)
                for(int k=0;k<(1<<n);++k)
                    if(((k<<1)&k)==0&&((k>>1)&k)==0)
					    if((j&k)==0&&(j&(k<<1))==0&&(j&(k>>1))==0)
						    for(int l=w;l>=t(j);--l)
							    f[i][j][l]+=f[i-1][k][l-t(j)];
	for(int i=0;i<(1<<n);++i) ans+=f[n][i][w];
	cout<<ans;
    return 0;
}
2022/10/6 13:05
加载中...