简答题
偏难
#20645
武器购买 时间限制:1.0 s 内存限制:512.0 MB 题面描述 商店里有 n 个武器,第 i 个武器的强度为 p i ,花费为 c i 。 小杨想要购买一…
武器购买
时间限制:1.0 s
内存限制:512.0 MB
题面描述
商店里有 n 个武器,第 i 个武器的强度为 pi,花费为 ci。
小杨想要购买一些武器,满足这些武器的总强度不小于 P ,总花费不超过 Q ,小杨想知道是否存在满足条件的购买方案,如果有,最少花费又是多少。
输入格式
第一行包含一个正整数 t ,代表测试数据组数。
对于每组测试数据,第一行包含三个正整数 n,P,Q,含义如题面所示。
之后 n 行,每行包含两个正整数 pi,ci,代表武器的强度和花费。
输出格式
对于每组测试数据,如果存在满足条件的购买方案,输出最少花费,否则输出 -1。
输入样例
输出样例

对于全部数据,保证有 1≤t≤10,1≤n≤100,1≤pi,ci,P,Q≤5×104。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[50010];
ll solve(int n, int P, int Q, vector<pair<int, int>>& weapons) {
dp[0] = 0;
for (auto& weapon : weapons) {
int p = weapon.first;
int c = weapon.second;
for (int j = Q; j >= c; --j) {
if (dp[j - c]>=0) {
dp[j] = max(dp[j], dp[j - c] + p);
}
}
}
for (int j = 0; j <= Q; ++j) {
if (dp[j] >= P) {
return j;
}
}
return -1;
}
int main() {
int t;
cin>>t;
while(t--){
int n, P, Q;
cin >> n >> P >> Q;
memset(dp,-0x3f,sizeof dp);
vector<pair<int, int> > weapons(n);
for (int i = 0; i < n; ++i) {
cin >> weapons[i].first >> weapons[i].second;
}
cout << solve(n, P, Q, weapons) << "\n";
}
return 0;
}</pre>
这道题暂未补解析。