ZOJ2898【折半搜索】

题意：

给出一系列值和对应的陷阱，对于陷阱如果存在两个就抵消，求价值最大。

思路：

折半枚举，利用异或

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int v[30],k[30];

int trap[30][60],n,ans;

map<LL,int>mp;

map<LL,int>::iterator it;

int main()

{

	while(~scanf("%d",&n))

	{

		ans=0;

		mp.clear();

		for(int i=0;i<n;i++)

		{

			scanf("%d",&v[i]);

			scanf("%d",&k[i]);

			for(int j=0;j<k[i];j++)

				scanf("%d",&trap[i][j]);

		}

		int half=n/2;

		int sz=(1<<half);

		for(int i=0;i<sz;i++)

		{

			LL x=0;

			int val=0;

			for(int j=0;j<half;j++)

			{

				if(i&(1<<j))

				{

					for(int t=0;t<k[j];t++)

						x^=(LL)(1LL<<trap[j][t]);

					val+=v[j];

				}

			}

			it=mp.find(x);

			if(it!=mp.end())

			{

				int last=it->second;

				if(last<val)

					mp[x]=val;

			}

			else

				mp[x]=val;

		}

		int res=n-half;

		sz=(1<<res);

		for(int i=0;i<sz;i++)

		{

			LL x=0;

			int val=0;

			for(int j=0;j<res;j++)

			{

				if(i&(1<<j))

				{

					for(int t=0;t<k[j+half];t++)

						x^=(LL)(1LL<<trap[j+half][t]);

					val+=v[j+half];

				}

			}

			LL y=(0LL^x);

			it=mp.find(y);

			if(it!=mp.end())

			{

				int now=it->second;

				val+=now;

				ans=max(ans,val);

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

ZOJ2898【折半搜索】

最新文章

热门文章