[训练指南]UVa11825 状压dp 集合问题 二进制状态枚举所有集合

感觉如果早知道那个快速枚举子集的算法的话其实也就很简单。。太弱了orz

这个问题可以抽象成,将n个集合划分成尽可能多的组,满足约束每个组里的集合之和(所有的相或)都是全集,在这里注意这里说的原本的集合是对应于题中的节点的,一个节点和与他相邻的所有节点这一坨东西算一个基本集合。N<=16,很容易想到用二进制数字来表示集合,比如P[1]=011010表示1节点对应的集合里有1,3,4这三个节点。然后要预处理出不同每个原来的集合之间相或的结果用cov表示,这里又用了一次二进制表示不同的集合,比如cov[000101]就表示第0个节点对应的集合和第3个节点对应的集合相或之后的结果,也就是P[0] | P[2],注意如果这里的cov==1<<N,那说明这个组合就可以使得某一个服务整体GG,因为这个cov里包含的P里包含的节点已经覆盖到了所有的节点了。

然后就是递推了,知道可以快速枚举出一个集合的子集的方法之后很容易写出递推方程f[S]=max(f[S-S1])+1    其中S1是S的子集且满足cov[S1]==1<<N,注意这里不一定要求S-S1满足这样的要求(这里我脑子抽了一开始写了这个判断

代码

#include 
#include 
#include 
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;
typedef long long LL;
const int maxn=(1<<16)+5;
const int MOD=1e9+7;

int P[20],cov[maxn],ans[maxn];

int main()
{
    int N,temp,k,cnt=0;
    while(~scanf("%d",&N)&&N)
    {
        cnt++;
        //memset(ans,0,sizeof(ans));
        for (int i=0;i>i)&1)
                {
                    cov[S]|=P[i];
                }
            }
        }
        for (int S=1;S<(1<
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据