HJ16 购物单

题目：https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&tqId=21239&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=

是个加了限制条件的背包问题。如果q[i]不等于0，那么你就必须买了编号为q[i]的商品才能购买编号为i的商品

注意到一个主件最多只会有两个附件，那就把每个主件带着它的附件合并成一个整体，num_fa是主件数。

对每个整体进行dp，dp[i][j]表示对于前i个整体花费了j元能得到的最大满意度。然后对于每个整体，dp的过程中拆开来维护一下里面的两个附件是否要购买就可以了。

注意到价格只会是10的整数，所以对于价格整体除以10，这样循环的层数可以少10倍，会快一些。输出结果时再把10乘回去就行。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,dp[65][3202],duiying[65],num_fa=0;
 4 struct SP{
 5     int v,p,q,id;
 6 }a[65];
 7 struct Bag{
 8     int v,p,id,num_son;
 9     int sv[3],sp[3],sid[3];
10 }b[65];
11 void init(){
12     cin>>n>>m;
13     n/=10;
14     for(int i=1;i<=m;i++){
15         scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);
16         a[i].v/=10;
17         a[i].id=i;
18     }
19     for(int i=1;i<=m;i++){
20         if(a[i].q==0){
21             b[++num_fa].id=a[i].id;
22             b[num_fa].p=a[i].p;
23             b[num_fa].v=a[i].v;
24             for(int j=1;j<=m;j++){
25                 if(a[j].q==b[num_fa].id){
26                     b[num_fa].num_son++;
27                     b[num_fa].sv[b[num_fa].num_son]=a[j].v;
28                     b[num_fa].sp[b[num_fa].num_son]=a[j].p;
29                     b[num_fa].sid[b[num_fa].num_son]=a[j].id;
30                 }
31             }
32         }
33     }
34     return;
35 }
36 void Work(){
37     for(int i=1;i<=num_fa;i++){
38         for(int j=0;j<=n;j++){
39             if(j>=b[i].v){
40                 dp[i][j]=max(dp[i][j],dp[i-1][j-b[i].v]+b[i].v*b[i].p);
41                 for(int k=1;k<=b[i].num_son;k++){
42                     if(j>=b[i].v+b[i].sv[k])
43                         dp[i][j]=max(dp[i][j],dp[i-1][j-b[i].v-b[i].sv[k]]
44                         +b[i].v*b[i].p+b[i].sv[k]*b[i].sp[k]);
45                 }
46                 if(b[i].num_son==2&&j>=b[i].v+b[i].sv[1]+b[i].sv[2])
47                     dp[i][j]=max(dp[i][j],dp[i-1][j-b[i].v-b[i].sv[1]-b[i].sv[2]]
48                         +b[i].v*b[i].p+b[i].sv[1]*b[i].sp[1]+b[i].sv[2]*b[i].sp[2]);
49             }
50             dp[i][j]=max(dp[i][j],dp[i-1][j]);
51         }
52     }
53     return;
54 }
55 void Output(){
56     printf("%d\n",dp[num_fa][n]*10);
57     return;
58 }
59 int main(){
60     init();
61     Work();
62     Output();
63     return 0;
64 }