hdu_3182_Hamburger Magi(状压DP)

时间:2023-03-09 22:11:56
hdu_3182_Hamburger Magi(状压DP)

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3182

题意:有n个汉堡,做每个汉堡需要消耗一定的能量,每个汉堡对应一定的价值,且只能做一次,并且做当前汉堡需要先做出列出的汉堡,求最大的价值

题解:状压DP

 #include<cstdio>
#define FFC(i,a,b) for(int i=a;i<=b;++i) int T,n,all,end,now,cur,ans,flag,v[],e[],a[][],dp[<<],c[<<]; int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&all),end=(<<n)-,c[]=all;
FFC(i,,n)scanf("%d",&v[i]);FFC(i,,n)scanf("%d",&e[i]);
FFC(i,,n){
scanf("%d",&a[i][]);
FFC(j,,a[i][])scanf("%d",&a[i][j]);
}
FFC(i,,end)dp[i]=-;
dp[]=,ans=;
FFC(i,,end){
if(dp[i]==-)continue;
FFC(j,,n-){
now=<<j,flag=,cur=now|i;
if((i&now)==&&c[i]>=e[j+]){
FFC(k,,a[j+][])if(((<<(a[j+][k]-))&i)==){flag=;break;}
if(flag)continue;
if(dp[cur]<dp[i]+v[j+])
dp[cur]=dp[i]+v[j+],c[cur]=c[i]-e[j+],ans=ans>dp[cur]?ans:dp[cur];
}
}
}
printf("%d\n",ans);
}
return ;
}