HDU 3182 Hamburger Magi

HDU 3182 Hamburger Magi

题目：.php?pid=3182

题意：有n个汉堡，每个汉堡有一个价值和做汉堡需要的体力，并且做有些汉堡前需要先做别的汉堡，问最多能做出多大价值

每个汉堡只能做一次并且有先后顺序，所以需要状压dp而不能直接暴力判断

做汉堡的前置关系可以用状压来简化判断

还可以预处理出每个状态需要花费的体力

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
int n,m,maxx;
int cost[1<<15];
int a[20];
int dp[1<<15];
int v[20],e[20];
int main()
{ios::sync_with_stdio(false);int T;cin>>T;while(T--){cin>>n>>m;for(int i=0;i<n;i++)cin>>v[i];for(int i=0;i<n;i++)cin>>e[i];for(int i=0;i<n;i++){a[i]=0;int x,y;cin>>x;while(x--){cin>>y;y--;a[i]|=(1<<y);}}int tot=1<<n;memset(cost,0,sizeof(cost));for(int i=0;i<tot;i++){for(int j=0;j<n;j++)if ((i>>j)&1)cost[i]+=e[j];}memset(dp,-1,sizeof(dp));dp[0]=0;maxx=0;for(int i=0;i<tot;i++){if (dp[i]==-1) continue;for(int j=0;j<n;j++){if ((i>>j)&1) continue;if (cost[i]+e[j]>m) continue;if ((i&a[j])==a[j]){dp[i|(1<<j)]=dp[i]+v[j];maxx=max(maxx,dp[i|(1<<j)]);}}}cout<<maxx<<endl;}return 0;
}

转载于:.html