状态压缩 HDU 3182

t组数据

n个汉堡 e的能量

接下来的2行

val    n个 得到的权

cost  n个 花去的能量

接下来n行

每行一个q  q个数字

代表这类汉堡做好要的前提  每个汉堡只能用一次

#include<stdio.h>

#include<algorithm>

#include<string.h>

using namespace std;

#define MAXN 1<<15

int dp[MAXN];

int val[],co[];

int x[];

int cost[MAXN];

int n,e;

void Init()  //预处理出所有状态要的能量

{

    int en=(<<n);

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

    {

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

        {

            if((i&(<<j)))

                cost[i]+=co[j];

        }

    }

}

bool jud(int state,int p)  //判断这个状态是否合法

{

    if((state&x[p])==x[p]&&cost[state]+co[p]<=e)

        return ;

    return ;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&e);

        memset(dp,-,sizeof(dp));

        memset(cost,,sizeof(cost));

        memset(x,,sizeof(x));

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

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

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

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

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

        {

            int a;

            scanf("%d",&a);

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

            {

                int b;

                scanf("%d",&b);

                b--;

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

            }

        }

        Init();

        int ans=;

        dp[]=;

        int en=(<<n);

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

        {

            if(dp[i]!=-)

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

                {

                    if(jud(i,j)&&(i&(<<j))==) /这个汉堡可以做

                    {

                        dp[i|(<<j)]=dp[i]+val[j]; //前面的权值+这个的权

                        ans=max(ans,dp[i|(<<j)]);

                    }

                }

        }

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

    }

    return ;

}