A29814. 武器购买
填空题
困难
知识点
题目描述
武器购买
时间限制：1.0 s 内存限制：512.0 MB
题目描述
商店里有n个武器，第i个武器的强度为 pi，花费为 ci。
小杨想要购买一些武器，满足这些武器的总强度不小于P，总花费不超过Q，小杨想知道是否存在满足条件的购买方案，如果有，最少花费又是多少。
输入格式
第一行包含一个正整数 t，代表测试数据组数。
对于每组测试数据，第一行包含三个正整数 n, P, Q，含义如题目所示。
之后 n 行，每行包含两个正整数 pi , ci ，代表武器的强度和花费。
输出格式
对于每组测试数据，如果存在满足条件的购买方案，输出最少花费，否则输出 -1。
输入样例
3
3 2 3
1 2
1 2
2 3
3 3 4
1 2
1 2
2 3
3 1000 1000
1 2
1 2
2 3
1输出样例
3
-1
-1参考答案
#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;
}
上一题
下一题