题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3182
题意：有n个汉堡，做每个汉堡需要消耗一定的能量，每个汉堡对应一定的价值，且只能做一次，并且做当前汉堡需要先做出列出的汉堡，求最大的价值
题解：状压DP
1 #include<cstdio> 2 #define FFC(i,a,b) for(int i=a;i<=b;++i) 3 4 int T,n,all,end,now,cur,ans,flag,v[16],e[16],a[16][16],dp[1<<16],c[1<<16]; 5 6 int main(){ 7 scanf("%d",&T); 8 while(T--){ 9 scanf("%d%d",&n,&all),end=(1<<n)-1,c[0]=all; 10 FFC(i,1,n)scanf("%d",&v[i]);FFC(i,1,n)scanf("%d",&e[i]); 11 FFC(i,1,n){ 12 scanf("%d",&a[i][0]); 13 FFC(j,1,a[i][0])scanf("%d",&a[i][j]); 14 } 15 FFC(i,0,end)dp[i]=-1; 16 dp[0]=0,ans=0; 17 FFC(i,0,end){ 18 if(dp[i]==-1)continue; 19 FFC(j,0,n-1){ 20 now=1<<j,flag=0,cur=now|i; 21 if((i&now)==0&&c[i]>=e[j+1]){ 22 FFC(k,1,a[j+1][0])if(((1<<(a[j+1][k]-1))&i)==0){flag=1;break;} 23 if(flag)continue; 24 if(dp[cur]<dp[i]+v[j+1]) 25 dp[cur]=dp[i]+v[j+1],c[cur]=c[i]-e[j+1],ans=ans>dp[cur]?ans:dp[cur]; 26 } 27 } 28 } 29 printf("%d ",ans); 30 } 31 return 0; 32 }