HDU3182 Hamburger Magi【状压DP】

HDU3182 Hamburger Magi【状压DP】

题目链接：Hamburger Magi

分析：每种汉堡只能做一次，恰好就是0～(1<<n)-1的所有状态；

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=(1<<15)+100;
int dp[maxn];
struct node{int val,cost,a;} p[20];
void rua()
{int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++) scanf("%d",&p[i].val);for(int i=0;i<n;i++) scanf("%d",&p[i].cost);for(int i=0;i<n;i++){int kk;scanf("%d",&kk);p[i].a=0;while(kk--){int x;scanf("%d",&x);p[i].a|=(1<<(x-1));}}memset(dp,-1,sizeof(dp));dp[0]=0;for(int i=0;i<(1<<n);i++){if(dp[i]==-1) continue;int tot=0;for(int j=0;j<n;j++) if(i&(1<<j)) tot+=p[j].cost;if(tot>m) continue;for(int j=0;j<n;j++)if((i&(1<<j))==0 && (p[j].a&i)==p[j].a && tot+p[j].cost<=m) dp[i|(1<<j)]=max(dp[i|(1<<j)],dp[i]+p[j].val);}int ans=0;for (int i=0;i<(1<<n);i++) ans=max(ans,dp[i]);printf("%dn",ans);
}
int main()
{int t;scanf("%d",&t);while(t--) rua();return 0;
}