洛谷 P1060 [NOIP2006 普及组] 开心的金明

自用。

题目传送门：[NOIP2006 普及组] 开心的金明 - 洛谷

题解：Inori_333

参考题解：题解 P1060 【开心的金明】 - 洛谷专栏

/*P1060 [NOIP2006 普及组] 开心的金明https://www.luogu.com.cn/problem/P10602024/10/24  submit:inori_333
*/#include<bits/stdc++.h>
using namespace std;
int n, m;//总钱数和希望购买的物品个数
int v[25], p[25];//v[i]表示第i个物品的价格，p[i]表示第i个物品的重要度
int dp[30005];//dp[i]表示总钱数为i时的最大重要度int main(){cin >> n >> m;for (int i = 1; i <= m;i++){cin >> v[i] >> p[i];p[i] *= v[i];}for (int i = 1; i <= m;i++){for (int j = n; j >= v[i];j--){dp[j] = max(dp[j], dp[j - v[i]] + p[i]);}}cout << dp[n];
}