金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。

更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。

今天一早，金明就開始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：

如果要買歸類為附件的物品，必須先買該附件所屬的主件。

每個主件可以有0個、1個或2個附件。

附件不再有從屬于自己的附件。

金明想買的東西很多，肯定會超過媽媽限定的N元。

于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)1~5表示，第5等最重要。

他還從因特網(wǎng)上查到了每件物品的價格（都是10元的整數(shù)倍）。

他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。

設(shè)第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1，j2，…，jk，則所求的總和為：

v[j1]?w[j1]+v[j2]?w[j2]+…+v[jk]?w[jk]（其中*為乘號）

請你幫助金明設(shè)計一個滿足要求的購物單。

輸入格式

輸入文件的第1行，為兩個正整數(shù)，用一個空格隔開：N m，其中N表示總錢數(shù)，m為希望購買物品的個數(shù)。

從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數(shù)據(jù)，每行有3個非負整數(shù)v p q，其中v表示該物品的價格，p表示該物品的重要度（1~5），q表示該物品是主件還是附件。

如果q=0，表示該物品為主件，如果q>0，表示該物品為附件，q是所屬主件的編號。

輸出格式

輸出文件只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（<200000）。

數(shù)據(jù)范圍

N<32000,m<60,v<10000

?

#include <bits/stdc++.h>#define v first #define w secondusing namespace std;typedef pair<int, int> PII;const int N = 60, M = 32010;int n, m; PII master[N]; vector<PII> servent[N]; int f[M];int main() {cin >> m >> n;for (int i = 1; i <= n; i ++ ){int v, p, q;cin >> v >> p >> q;p *= v;if (!q) master[i] = {v, p};else servent[q].push_back({v, p});}for (int i = 1; i <= n; i ++ )for (int u = m; u >= 0; u -- ){for (int j = 0; j < 1 << servent[i].size(); j ++ ){int v = master[i].v, w = master[i].w;for (int k = 0; k < servent[i].size(); k ++ )if (j >> k & 1){v += servent[i][k].v;w += servent[i][k].w;}if (u >= v) f[u] = max(f[u], f[u - v] + w);}}cout << f[m]; }

總結(jié)

以上是生活随笔為你收集整理的AcWing 487. 金明的预算方案的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。