UVA11825 Hacker's Crackdown 二进制集合+关于子集的动态规划

题意：有N台服务器，全部服务器都直接运行着完全相同的N个任务。对于每台电脑，你都可以进行“一次”操作，使得某（自己选定）一种任务停止，且同时会使得其他和这台服务器直接相连的电脑上面相同的服务完全终止。问题是：能够使得几种不同的任务完全消失在这N个服务器当中。

数学模型：选择若干个给定的子集，最多可以将全集覆盖多少次。

首先，使用整数来表示不同的集合，理由是正好对应了，1,0两种不同的数值，也可以分别对应选取和不选两种不同的状态。

因而，此处首先使用整数来代指选了的电脑的集合——010代表选择1号机器其十进制值是2.

因而，我们可以进行强行穷举：设DP[I]选择I代表的集合可以得到的最覆盖次数。可以得到一个性质，如果DP[I]的值不为0，就意味着集合I至少覆盖了全集一次，否则应当认为，其不构成全集一次。

于是，枚举所有能够构成全集的子集和，认为，当前状态应当为，至少构成了一次的全集的子集的补集的DP值+1，从中找到一个最大的。

自己也被绕进去了。。GG看代码吧

#include<bits/stdc++.h>

using namespace std;

const long long MAXN=;

long long f[MAXN];

long long cover[MAXN];

long long p[];

int n,ans;

void init()

{

//    memset(f,0,sizeof(f));

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

    {

        p[i]=(<<i);

        int x,m;

        cin>>m;

        while(m--)

        {

            cin>>x;

            p[i]|=(<<x);

        }

    }

    int limit=<<n;

    for(int s=;s<limit;++s)

    {

        cover[s]=;

        f[s]=;

        for(int j=;j<n;++j)

        {

            if(s&(<<j))cover[s]|=p[j];

        }

    }

    f[]=;

    long long ALL=(<<n)-;

    for(int s=;s<limit;++s)

    {

        for(int ss=s;ss;ss=(ss-)&s)

            if(cover[ss]==ALL)f[s]=max(f[s],f[ss^s]+);

    }

    ans=f[ALL];

}

int main()

{

    cin.sync_with_stdio(false);

    long long kk=;

    while(cin>>n&&n)

    {

        init();

        cout<<"Case "<<kk++<<": "<<ans<<endl;

    }

    return ;

}

巴特西

UVA11825 Hacker's Crackdown 二进制集合+关于子集的动态规划

最新文章

热门文章