爆零
  • 板块B3618 寻找团伙
  • 楼主theb0t
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/1/4 21:59
  • 上次更新2024/1/5 13:22:45
查看原帖
爆零
997236
theb0t楼主2024/1/4 21:59

这个没有优化的dfs怎么可能一分没得呢?怎么优化呢?

#include<iostream>
#include<cmath>
#include<cstring>
#define int long long
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

int n,k;
struct p{
	int c;
	int d[65];
};
p a[25];
int b[65];
int ans=-1;
void dfs(int ceng)
{
	if(ceng==n+1)
	{
		int sum=0;
		for(int i=1;i<=k;i++)
			if(b[i]%2!=0) sum+=pow(2,k-i);
		ans=max(ans,sum);
		return;
	}
	for(int i=1;i<=a[ceng].c;i++)
		b[a[ceng].d[i]]++;
	dfs(ceng+1);
	
	for(int i=1;i<=a[ceng].c;i++)
		b[a[ceng].d[i]]--;
	dfs(ceng+1);
}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].c;
		for(int j=1;j<=a[i].c;j++) cin>>a[i].d[j];
	}
	dfs(1);
	cout<<ans<<endl;
	return 0;
}

2024/1/4 21:59
加载中...