原题地址 https://www.luogu.org/problemnew/show/U65320
OakOak 便帮助 金明 解决了他的 预算方案 问题：
金明 今天很开心，家里购置的新房就要领钥匙了，新房里有一间 金明 自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 NN 元钱就行”。今天一早， 金明 就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
| 主件 | 附件 |
| 电脑 | 打印机，扫描仪 |
| 书柜 | 图书 |
| 书桌 | 台灯，文具 |
| 工作椅 | 无 |
如果要买归类为附件的物品，必须先买该附件所属的主件。附件不再有从属于自己的附件。 金明 想买的东西很多，肯定会超过妈妈限定的 NN 元。于是，他把每件物品规定了一个重要度，分为 kk 等：用整数 1\sim k1∼k 表示，第 kk 等最重要。他还从因特网上查到了每件物品的价格。他希望在不超过 NN 元（可以等于 NN 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 jj 件物品的价格为 v[j]v[j] ，重要度为 p[j]p[j] ，共选中了 kk 件物品，编号依次为 j_1,j_2,...,j_kj1?,j2?,...,jk? ，则所求的总和为：
v[j_1]\times p[j_1]+v[j_2]\times p[j_2]+...+v[j_k]\times p[j_k]v[j1?]×p[j1?]+v[j2?]×p[j2?]+...+v[jk?]×p[jk?]
现在 OakOak 不满足于解决这类简单的问题(因为他需要购置满满一大卡车的物品)，于是他请你帮忙设计一个程序帮他处理那数据规模庞大的物品清单。
第11行，为两个正整数，用一个空格隔开：N\;mNm（其中NN表示总钱数，mm为希望购买物品的个数。）
从第22行到第m+1m+1行，第ii行给出了编号为i-1i−1的物品的基本数据，每行有33个非负整数 v_{i-1}\;p_{i-1}\;q_{i-1}vi−1?pi−1?qi−1? （其中v_{i-1}vi−1?表示该物品的价格，p_{i-1}pi−1?表示该物品的重要度，q_{i-1}qi−1?表示该物品是主件还是附件。如果 q_{i-1}=0qi−1?=0，表示该物品为主件，如果 q_{i-1}>0qi−1?>0，表示该物品为附件，q_{i-1}qi−1?是所属主件的编号）
一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值。
1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0
2200
10000 20 300 2 0 500 2 1 200 4 1 800 1 1 600 5 1 650 3 1 600 3 1 750 2 1 650 1 1 850 4 1 550 3 1 850 2 1 700 4 1 950 1 1 950 5 1 700 5 1 500 2 1 650 3 1 800 3 1 850 4 1
金明的预算方案升级版，当初做金明的预算方案时想的是树上背包，好，建树，开始DP，然后TLE哈哈哈哈。后来想了想，其实可以在每一个主件的附件做一次背包，然后再
在主件中做一次背包，问题就解决啦。开开心心码完，A了金明。去题解区看看有没有更好的做法，然后在题解中看到了Oak的预算方案，刚A完题，心情澎湃，这题我也能A。然后
就……就……
其实正解也是后来的这个想法，不过我实现的方式不好，所以……所以就去题解区%%
以下是正解，前面是废话哈哈哈哈。
首先我们需要两个数组，DP1[i][j]表示前i个物品用j元能得到的最大收益，然后逆序枚举，就能省掉i的这一维。DP2[i][j]表示前i个物品，用了j元，且考虑完第i个物品的附件时，能
得到的最大收益，同样可以省掉i的这一维。两者有什么不同？DP2[i]其实表示的是，必须买第i个物品，而DP1[i]则不一定。 (有没有很熟悉？想一想最大子串和？f[i]表示以i结尾的最大子串
和,i必须选，，g[i]表示前i个数字的最大子串和，g[i]=max(g[i],f[i])，最后就不用再扫一遍找f[i]的最大值啦） 这道题也一样用到了这个思想，所以DP1[i]=max(DP1[i],DP2[i]).
好了，空口无凭，来人啊，上代码。
#include<bits/stdc++.h> #define maxn 500001 using namespace std; struct node { int v;int imp;int fa; node(){} node(int a,int b,int c){v=a;imp=a*b;fa=c;} }arr[1001]; int n,m; int dp1[maxn],dp2[maxn]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); arr[i]=node(a,b,c);//a 表示该物品的价格，b表示买了这个物品能得到的收益，c表示 } //该物品的主件 for(int i=1;i<=m;i++)//枚举每一件物品 { if(!arr[i].fa)//如果它是主件 { for(int j=0;j<arr[i].v;j++) dp2[j]=0; //第i个物品必须买，所以小于其价格的自然设为0 for(int j=arr[i].v;j<=n;j++) dp2[j]=dp1[j-arr[i].v]+arr[i].imp; //第i个物品必须买，所以——这个公式显然成立哈哈哈 for(int j=1;j<=m;j++) if(arr[j].fa==i)//找第i个物品的附件 for(int k=n;k>=arr[i].v+arr[j].v;k--) //循环变量边界设为arr[i].v+arr[j].v保证能够买第i个物品，以及附件j dp2[k]=max(dp2[k-arr[j].v]+arr[j].imp,dp2[k]); //这个公式，也显然成立…… for(int j=arr[i].v;j<=n;j++) dp1[j]=max(dp1[j],dp2[j]);//就是之前说的咯 } } printf("%d",dp1[n]); return 0; }
总结：很多难搞的DP，开个辅助数组是很用的哈。像是之前的那一篇博客打砖块，开了两个DP数组。学到了学到了哈哈哈
原文：https://www.cnblogs.com/lee454207074/p/11765671.html