题目487. 金明的预算方案题目描述金明今天很开心家里购置的新房就要领钥匙了新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是妈妈昨天对他说“你的房间需要购买哪些物品怎么布置你说了算只要不超过N NN元钱就行”。今天一早金明就开始做预算了他把想买的物品分为两类主件与附件附件是从属于某个主件的下表就是一些主件与附件的例子如果要买归类为附件的物品必须先买该附件所属的主件。每个主件可以有0 00个、1 11个或2 22个附件。附件不再有从属于自己的附件。金明想买的东西很多肯定会超过妈妈限定的N NN元。于是他把每件物品规定了一个重要度分为5 55等用整数1 − 5 1-51−5表示第5 55等最重要。他还从因特网上查到了每件物品的价格都是10 1010元的整数倍。他希望在不超过N NN元可以等于N NN元的前提下使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v [ j ] v[j]v[j]重要度为w [ j ] w[j]w[j]共选中了k kk件物品编号依次为j 1 j 2 … j k j_1j_2…j_kj1j2…jk则所求的总和为v [ j 1 ] ∗ w [ j 1 ] v [ j 2 ] ∗ w [ j 2 ] … v [ j k ] ∗ w [ j k ] v[j_1]∗w[j_1]v[j_2]∗w[j_2]…v[j_k]∗w[j_k]v[j1]∗w[j1]v[j2]∗w[j2]…v[jk]∗w[jk]其中∗ *∗为乘号请你帮助金明设计一个满足要求的购物单。输入格式输入文件的第1 11行为两个正整数用一个空格隔开N NN,m mm其中N NN表示总钱数m mm为希望购买物品的个数。从第2 22行到第m 1 m1m1行第j jj行给出了编号为j − 1 j−1j−1的物品的基本数据每行有3 33个非负整数v , p , q v,p,qv,p,q其中v vv表示该物品的价格p pp表示该物品的重要度 1 − 5 1-51−5q qq表示该物品是主件还是附件。如果q 0 q0q0表示该物品为主件如果q 0 q0q0表示该物品为附件q qq是所属主件的编号。输出格式输出文件只有一个正整数为不超过总钱数的物品的价格与重要度乘积的总和的最大值 200000 200000200000。数据范围N 32000 , m 60 , v 10000 N32000,m60,v10000N32000,m60,v10000时空限制1s / 128MB输入样例1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0输出样例2200代码1二维数组#includebits/stdc.husingnamespacestd;constintN6010,M3200010;intn,V,cnt,f[N][M],vv,ww;structnode{intv,w;}g1[N];vectornodeg2[N];intmain(){cinVn;for(inti1;in;i){inta,b,c;cinabc;if(!c){g1[i]{a,a*b};}elseg2[c].push_back({a,a*b});}for(inti1;in;i)for(intj0;jV;j){f[i][j]f[i-1][j];if(g1[i].vj){intleng2[i].size();for(intk0;k(1len);k){vvg1[i].v,wwg1[i].w;for(intu0;ulen;u)if(ku1){vvg2[i][u].v;wwg2[i][u].w;}if(vvj)f[i][j]max(f[i][j],f[i-1][j-vv]ww);}}}coutf[n][V];return0;}代码2一维数组#includeiostream#includevector#definevfirst#definewsecondusingnamespacestd;typedefpairint,intPII;constintMaxN6010,MaxV3200010;intN,V,f[MaxV];PII m[MaxN];vectorPIIs[MaxN];intmain(){cinVN;for(inti1;iN;i){inta,b,q;cinabq;if(!q){m[i]{a,a*b};}else{s[q].push_back({a,a*b});}}for(inti1;iN;i){if(m[i].v){for(intjV;j0;j--){for(intk0;k1s[i].size();k){intvm[i].v,wm[i].w;for(intu0;us[i].size();u){if(ku1){vs[i][u].v;ws[i][u].w;}}if(vj){f[j]max(f[j],f[j-v]w);}}}}}coutf[V];return0;}结果
