Hamburger Magi
问题描述 :
In the mysterious forest, there is a group of Magi. Most of them like to eat human beings, so they are called “The Ogre Magi”, but there is an special one whose favorite food is hamburger, having been jeered by the others as “The Hamburger Magi”.
Let’s give The Hamburger Magi a nickname “HamMagi”, HamMagi don’t only love to eat but also to make hamburgers, he makes N hamburgers, and he gives these each hamburger a value as Vi, and each will cost him Ei energy, (He can use in total M energy each day). In addition, some hamburgers can’t be made directly, for example, HamMagi can make a “Big Mac” only if “New Orleams roasted burger combo” and “Mexican twister combo” are all already made. Of course, he will only make each kind of hamburger once within a single day. Now he wants to know the maximal total value he can get after the whole day’s hard work, but he is too tired so this is your task now!
Let’s give The Hamburger Magi a nickname “HamMagi”, HamMagi don’t only love to eat but also to make hamburgers, he makes N hamburgers, and he gives these each hamburger a value as Vi, and each will cost him Ei energy, (He can use in total M energy each day). In addition, some hamburgers can’t be made directly, for example, HamMagi can make a “Big Mac” only if “New Orleams roasted burger combo” and “Mexican twister combo” are all already made. Of course, he will only make each kind of hamburger once within a single day. Now he wants to know the maximal total value he can get after the whole day’s hard work, but he is too tired so this is your task now!
输入:
The first line consists of an integer C(C<=50), indicating the number of test cases.
The first line of each case consists of two integers N,E(1<=N<=15,0<=E<=100) , indicating there are N kinds of hamburgers can be made and the initial energy he has.
The second line of each case contains N integers V1,V2…VN, (Vi<=1000)indicating the value of each kind of hamburger.
The third line of each case contains N integers E1,E2…EN, (Ei<=100)indicating the energy each kind of hamburger cost.
Then N lines follow, each line starts with an integer Qi, then Qi integers follow, indicating the hamburgers that making ith hamburger needs.
The first line of each case consists of two integers N,E(1<=N<=15,0<=E<=100) , indicating there are N kinds of hamburgers can be made and the initial energy he has.
The second line of each case contains N integers V1,V2…VN, (Vi<=1000)indicating the value of each kind of hamburger.
The third line of each case contains N integers E1,E2…EN, (Ei<=100)indicating the energy each kind of hamburger cost.
Then N lines follow, each line starts with an integer Qi, then Qi integers follow, indicating the hamburgers that making ith hamburger needs.
输出:
The first line consists of an integer C(C<=50), indicating the number of test cases.
The first line of each case consists of two integers N,E(1<=N<=15,0<=E<=100) , indicating there are N kinds of hamburgers can be made and the initial energy he has.
The second line of each case contains N integers V1,V2…VN, (Vi<=1000)indicating the value of each kind of hamburger.
The third line of each case contains N integers E1,E2…EN, (Ei<=100)indicating the energy each kind of hamburger cost.
Then N lines follow, each line starts with an integer Qi, then Qi integers follow, indicating the hamburgers that making ith hamburger needs.
The first line of each case consists of two integers N,E(1<=N<=15,0<=E<=100) , indicating there are N kinds of hamburgers can be made and the initial energy he has.
The second line of each case contains N integers V1,V2…VN, (Vi<=1000)indicating the value of each kind of hamburger.
The third line of each case contains N integers E1,E2…EN, (Ei<=100)indicating the energy each kind of hamburger cost.
Then N lines follow, each line starts with an integer Qi, then Qi integers follow, indicating the hamburgers that making ith hamburger needs.
样例输入:
1 4 90 243 464 307 298 79 58 0 72 3 2 3 4 2 1 4 1 1 0
样例输出:
298
dp【statu】表示在该状态下消耗的能量 获得的价值
从0到大递推即可
AC代码如下：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct Node{ int id[101]; int tot; }; struct DP{ int sumv; int sume; }dp[1<<16]; int v[101], e[101]; int N, E; Node node[101]; int main(){ int T; cin >> T; while( T-- ){ cin >> N >> E; for( int i = 1; i <= N; i++ ){ cin >> v[i]; } for( int i = 1; i <= N; i++ ){ cin >> e[i]; } for( int i = 1; i <= N; i++ ){ cin >> node[i].tot; for( int j = 0; j < node[i].tot; j++ ){ cin >> node[i].id[j]; } } memset( dp, -1, sizeof( dp ) ); dp[0].sume = dp[0].sumv = 0; for( int i = 0; i < ( 1 << N ); i++ ){ if( dp[i].sume == -1 ){ continue; } for( int j = 1; j <= N; j++ ){ if( i & ( 1 << ( j - 1 ) ) ){ continue; } int flag = 1; for( int k = 0; k < node[j].tot; k++ ){ if( !( i & ( 1 << ( node[j].id[k] - 1 ) ) ) ){ flag = 0; break; } } if( flag == 1 ){ dp[i|(1<<(j-1))].sumv = dp[i].sumv + v[j]; dp[i|(1<<(j-1))].sume = dp[i].sume + e[j]; } } } int ans = 0; for( int i = 0; i < ( 1 << N ); i++ ){ if( dp[i].sume <= E ){ ans = max( ans, dp[i].sumv ); } } cout << ans << endl; } return 0; }
参考：http://blog.csdn.net/hzh_0000/article/details/20943319
(adsbygoogle = window.adsbygoogle || []).push({});
在说“你行你上的人”我说了句好，然后果断抄起砖头打死了他。“我上了，该你了。”
在说“你行你上的人”我说了句好，然后果断抄起砖头打死了他。“我上了，该你了。”
在说“你行你上的人”我说了句好，然后果断抄起砖头打死了他。“我上了，该你了。”
在说“你行你上的人”我说了句好，然后果断抄起砖头打死了他。“我上了，该你了。”
在说“你行你上的人”我说了句好，然后果断抄起砖头打死了他。“我上了，该你了。”
在说“你行你上的人”我说了句好，然后果断抄起砖头打死了他。“我上了，该你了。”
没错的，九度OJ也有此题
多谢提醒。代码又编辑了一下
The site You have write is very nicely prepared and quite insightful thanks for nice posta?|
这怎么用Catalan数啊？求解答！
博主的C++功底真是好
I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts
目测会火
A猴子认识的所有猴子和B猴子认识的所有猴子都能认识，这句话用《爱屋及乌》描述比较容易理解……
88行是多余的，可以删除
根本过不了。。。。


Aloha Apparel Co. sells only the finest ready-to-travel clothing. Browse ourcurrent of products or sign-up for updates below.
Stay uploaded on our latest product releases,
be the first to find out about
upcoming sales and get free style tips from our blog. Unsubscribe at any time.


$def with (selectedAY, fullMountingPlan) $ title_string = 'Edit All Mountings and Quotas' $var title:$title_string $ home = ['/', 'Home'] $ editAll = ['#', title_string] $var hierarchy = [home, editAll]
Edit the mountings and quotas for the AY one year after the current AY.


Getting hurt skateboarding is as inevitable as shitting your pants after eating Indian food, we know what we are getting into when we play with fire. It does not matter if you are pro, or just a dad trying your kids board after a few cold ones, slamming happens to the best of us. A lot of injuries go untreated and end up getting worse as they heal improperly, which can cause major problems down the road. Neglected injuries are usually due to either lack of funds to cover a hospital bill, or just simple ignorance. To help, we put together a short gallery of the most common injuries in skating