A22017. 道具商店题目描术道具商店⾥有n件道具可供挑选。第i件道具可为玩家提升ai点攻击⼒，需要ci枚⾦币才能购买，每件道具只能购买一次。现在你有k枚⾦币，请问你最多可以提升多少点攻击⼒？
填空题
困难
知识点
题目描述
道具商店
题目描术
道具商店⾥有n件道具可供挑选。第i件道具可为玩家提升ai点攻击⼒，需要ci枚⾦币才能购买，每件道具只能购买一次。现在你有k枚⾦币，请问你最多可以提升多少点攻击⼒？
输入格式
第一行，两个正整数n,k，表示道具数量以及你所拥有的金币数量。
接下来n行，每行两个正整数ai,ci，表示道具所提升的攻击力点数，以及购买所需的金币数量。
输出格式
输出一⾏，一个整数，表⽰最多可以提升的攻击⼒点数。
样例
输入样例 1
3 5
99 1
33 2
11 3输出样例 1
132输入样例 2
4 100
10 1
20 11
40 33
100 99输出样例 2
110数据范围
对于60的测试点，保证1≤k≤500,1≤ci≤500。
对于所有测试点，保证1≤n≤500,1≤k≤109,1≤ai≤500,1≤ci≤109。
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 505;
const int oo = 1e9 + 10;
int n, k;
int f[N * N];
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i < N * N; i++)
f[i] = oo;
int s = 0;
for (int i = 1; i <= n; i++) {
int a, c;
scanf("%d%d", &a, &c);
s += c;
for (int j = s; j >= a; j--)
f[j] = min(f[j], f[j - a] + c);
}
int ans = 0;
for (int i = 0; i < N * N; i++)
if (f[i] <= k)
ans = i;
printf("%d\n", ans);
return 0;
}
上一题
下一题