题解：P14920 [GESP202512 六级] 道具商店
前言
题目传送门
没想到出题人这么良心，出了一道大水题。
思路讲解
很经典的一个背包问题。
根据个人习惯，\(m\) 表示金币数量，\(v\) 表示增加的攻击力，\(w\) 表示价格。
我们发现，\(m\) 的值非常大，如果用普通的01背包来做，超时超空间，我们考虑效率更高的动态规划方式。
定义 \(DP\)
我们发现 \(w_i\) 和 \(n\) 的值都小于 500，那么就算全部取完也不会超时。
定义 \(dp_i\) 表示当总价值为 \(i\) 的时候，最少花费的金币。
那么最终答案就是找到一个最大的数 \(j\)，使得 \(dp_j \le m\)。
状态转移
不过是和普通转移翻了一下。
原本是 \(dp_j=max(dp_j,dp_{j-w_i}+v_i)\)。
现在是 \(dp_j=min(dp_j,dp_{j-v_i}+w_i)\)。
AC Code
别忘了 \(dp\) 数组初始化为无穷大。
#include <bits/stdc++.h>
using namespace std;
int n, m, v[505], w[505], cur, dp[250005];
//cur 表示所有物品的价值之和
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> v[i] >> w[i];cur += v[i];}//输入for (int i = 1; i <= cur; i++){dp[i] = 0x3f3f3f3f;//初始化dp数组}for (int i = 1; i <= n; i++){for (int j = cur; j >= v[i]; j--){dp[j] = min(dp[j], dp[j - v[i]] + w[i]);//状态转移方程}}for (int i = cur; i >= 0; i--) //输出答案{if (dp[i] <= m){cout << i << endl;break;}}return 0;
}