考察:状态压缩dp
这道题是 91. 最短Hamilton路径 的变种
思路:
很容易在优先级问题上陷入死循环(仅限本蒟蒻),实际上一开始做的时候,第一个汉堡要求食材必须是0,等同于从0点出发.设置f[0]=0,其他都=-99999999这样就可以避免样例给的死循环问题.
以i状态更新可以达到的j状态,可以去掉一重循环,并且优化到一维.
注意:这道题消耗汉堡做其他的汉堡,不需要把消耗的汉堡价值减掉....
1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 #include <cstdio>
5 using namespace std;
6 const int N = 16,M = 110;
7 int n,m,val[N],eng[N],need[N],cost[1<<N];
8 int f[1<<N];
9 void inits()
10 {
11 for(int i=0;i<1<<n;i++) f[i] = -9999999;
12 f[0] = 0;
13 memset(cost,0,sizeof cost); memset(need,0,sizeof need);
14 for(int i=0;i<1<<n;i++)
15 for(int j=0;j<n;j++)
16 if(i>>j&1) cost[i]+=eng[j+1];
17 }
18 int main()
19 {
20 int T;
21 scanf("%d",&T);
22 while(T--)
23 {
24 int ans = 0;
25 scanf("%d%d",&n,&m);
26 for(int i=1;i<=n;i++) scanf("%d",&val[i]);
27 for(int i=1;i<=n;i++) scanf("%d",&eng[i]);
28 inits();
29 for(int i=1;i<=n;i++)
30 {
31 int t; scanf("%d",&t);
32 for(int j=1;j<=t;j++)
33 {
34 int tmp; scanf("%d",&tmp);
35 need[i] |=(1<<(tmp-1));
36 }
37 }
38 for(int i=0;i<1<<n;i++)
39 if(cost[i]<=m)
40 for(int j=0;j<n;j++)
41 {
42 if(i>>j&1) continue;
43 if((i|need[j+1])!=i||(cost[i|(1<<j)]>m)) continue;
44 f[i|(1<<j)] = max(f[i|(1<<j)],f[i]+val[j+1]);
45 ans = max(ans,f[i|(1<<j)]);
46 }
47 printf("%d\n",ans);
48 }
49 return 0;
50 }