G7009 [GESP202412 七级] 武器购买 题解

知识点：0-1背包、动态规划、阈值。

解题思路

以费用为背包容量，dp[j]表示恰好花费j时可得最大威力，倒序处理每件武器。扫描费用从小到大找首个威力至少P的状态。

为什么正确

0-1转移穷尽选取武器的子集，保留同费用最大威力足以判断达标；第一次达标的费用就是最小值。

易错点

不可达费用用-1，不能默认为0；费用不超预算Q但仍无法达标时输出-1。

复杂度

每组时间O(nQ)，空间O(Q)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--) {
        int n,P,Q;
        cin>>n>>P>>Q;
        vector<int>dp(Q+1,-1);
        dp[0]=0;
        while(n--) {
            int p,c;
            cin>>p>>c;
            for(int j=Q;j>=c;j--)if(dp[j-c]>=0)dp[j]=max(dp[j],dp[j-c]+p);
        }
        int ans=-1;
        for(int j=0;j<=Q;j++)if(dp[j]>=P) {
            ans=j;
            break;
        }
        cout<<ans<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。