HDU 3181 Hamburger Magi（状压DP）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pair<int,int>pil;
const int INF = 0x3f3f3f3f;
#define N 16
int dp[1<<N],s[1<<N];
int val[110],e[110];
int f[110];//所需状态
int c,n,E;
int main()
{
    int num,x;
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d%d",&n,&E);CLEAR(f,0);
        REPF(i,1,n)  scanf("%d",&val[i]);
        REPF(i,1,n)  scanf("%d",&e[i]);
        REPF(i,1,n)
        {
            scanf("%d",&num);
            while(num--)
            {
                scanf("%d",&x);
                f[i]|=(1<<(x-1));
            }
        }
        CLEAR(dp,-1);CLEAR(s,0);
        dp[0]=0;s[0]=E;int status=(1<<n)-1;
        for(int i=0;i<=status;i++)
        {
            if(dp[i]==-1)  continue;
            for(int j=1;j<=n;j++)
            {
                if(i&(1<<(j-1))) continue;
                if((i|f[j])!=i) continue;
                int st=i|(1<<(j-1));
                if(dp[st]<dp[i]+val[j]&&s[i]>=e[j])
                {
                    dp[st]=dp[i]+val[j];
                    s[st]=s[i]-e[j];
                }
            }
        }
        int ans=0;
        for(int i=0;i<=status;i++)
            ans=max(ans,dp[i]);
        printf("%d\n",ans);
    }
    return 0;
}