求助P1896 [SCOI2005] 互不侵犯70pts
  • 板块学术版
  • 楼主Cure_Wing
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/10/13 08:59
  • 上次更新2023/10/27 07:43:28
查看原帖
求助P1896 [SCOI2005] 互不侵犯70pts
394167
Cure_Wing楼主2022/10/13 08:59
/*
	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/13 08:59
加载中...