[GESP202412 七级] 武器购买 题解

lby_commandBlock · 2024-12-08 12:54:14 · 题解

前言

看到这些题目，就要想到这道题要用什么算法来做，例如这道题要动态规划。

下文中的 p_i,c_i 均与题目描述一致。

思路

按照动态规划的步骤进行思考。动态规划五部曲。

1. dp 数组以及下标的含义。

设 dp_{i,j} 为前 i 个武器中购买，总花费不超过 j，以最优策略购买武器后，武器的强度和。

2. 递推公式。

• 若 c_i > j，即该武器的花费大于了总花费（下文称预算），则 dp_{i,j} 就直接从 dp_{i-1,j} 进行转移。

• 若 c_i \leq j，即该武器的花费小于预算，就有买和不买两种情况。

3. dp 数组如何初始化。

由于 dp 要求最大的强度和，所以直接将 dp 数组初始化为 0 即可。

4. 遍历顺序。

由于求 dp_{i,j} 牵连到了前 i-1 个武器的最大强度，但 dp_{i,j} 不会牵连到 dp_{i,k}(k<j)，所以 i 需要按从小到大的顺序进行遍历，j 哪个顺序遍历都行。

5. 打印 dp 数组。

按照 dp 数组的含义，找到最小的一个 q(1 \leq q \leq Q)，使得 dp_{n,q} \geq P 即可。若没有任何一个 dp_{n,q} \geq P，则直接按题意输出 -1 即可。

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int T, n, P, Q, p[109], c[109], dp[109][50009];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> n >> P >> Q;
        for (int i = 1; i <= n; i++)
            cin >> p[i] >> c[i];
        // 初始状态
        memset(dp, 0, sizeof(dp));
        // DP
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Q; j++) {
                // 不买
                dp[i][j] = dp[i - 1][j];
                // 若可以买，就把买和不买取最大值
                if (c[i] <= j)
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i]] + p[i]);
            }
        }
        // 打印
        bool flag = true;
        for (int q = 1; q <= Q; q++) {
            if (dp[n][q] >= P) {
                cout << q << endl;
                flag = false;
                break;
            }
        }
        if (flag)
            cout << -1 << endl;
    }
    return 0;
}