HDU 3182

HDU 3182

HDU 3182-Hamburger Magi

典型的状态压缩dp的题目。莫名其妙的出bug，之后又莫名其妙的AC。
我觉得dp数组开结构体比开数组存的信息更丰富。

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;int n,e;int v[100],ee[100];
int ok[100];
struct data
{int v,e;
}dp[7+(1<<15)];int main()
{int T;scanf("%d",&T);while(T--){memset(ok,0x3f,sizeof ok);scanf("%d%d",&n,&e);for(int i=0;i<n;i++){scanf("%d",&v[i]);}for(int i=0;i<n;i++){scanf("%d",&ee[i]);}memset(ok,0,sizeof ok);for(int i=0;i<n;i++){int m;int sta=0;scanf("%d",&m);for(int j=0;j<m;j++){int x;scanf("%d",&x);x--;sta|=(1<<x);}ok[i]=sta;}memset(dp,-1,sizeof dp);dp[0].v=0;dp[0].e=0;for(int i=0;i<(1<<n);i++){for(int j=0;j<n;j++){if(!(i&(1<<j))&&(dp[i].v!=-1)){if((dp[i].e+ee[j]<=e)&&(dp[i].v+v[j]>dp[i+(1<<j)].v)&&((i&ok[j])==ok[j])){dp[i+(1<<j)].v=dp[i].v+v[j];dp[i+(1<<j)].e=dp[i].e+ee[j];}}}}int ans=dp[(1<<n)-1].v;for(int i=0;i<(1<<n);i++)ans=max(ans,dp[i].v);printf("%dn",ans);}return 0;
}