简答题
偏难
#16973
道具商店 题目描述 道具商店里有n件道具可供挑选 。第 i 件道具可为玩家提升 a i 点攻击力 ,需要 c i 枚金币才能购买 ,每件道具只能购买一次 。现在…
道具商店
题目描述
道具商店里有n件道具可供挑选 。第 i 件道具可为玩家提升 ai 点攻击力 ,需要 ci 枚金币才能购买 ,每件道具只能购买一次 。现在你有k枚金币 ,请问你最多可以提升多少点攻击力?
输入格式
第一行 ,两个正整数 n, k ,表示道具数量以及你所拥有的金币数量。
接下来 n行 ,每行两个正整数 ai , ci ,表⽰道具所提升的攻击力点数, 以及购买所需的金币数量。
输出格式
输出一行,一个整数 ,表示最多可以提升的攻击力点数。
输入样例 1
3 5
99 1
33 2
11 3
输出样例 1
132
输入样例 2
1 4 100
2 10 1
3 20 11
4 40 33
5 100 99
输出样例 2
110
数据范围
对于 60 的测试点,保证 1 ≤ k ≤ 500,1 ≤ ci ≤ 500 。
对于所有测试点,保证 1 ≤ n ≤ 500,1≤ k ≤ 109 ,1≤ ai ≤ 500, 1≤ ci ≤ 109。
答案与解析
正确答案:<pre class="brush:python;toolbar:false">getint = lambda: map(int, input().split())
getints = lambda: list(getint())
# 得到物品数量和预算
n, k = getint()
# 这里进行了滚动优化,dp[j]表示攻击力为j的情况下的最小预算
# 最大攻击力为500*500,所以初始化这么大的数组,并且所有值都是1e10表示无穷大预算
f = [0] + [int(1e10)] * 500 * 500
# 能够达到的最大攻击力,用来缩小遍历的范围
s = 0
for i in range(n):
# 输入当前物品的攻击力和价格
a, c = getint()
s += a
# 计算题解中的转移公式,因为j是从高到低遍历的,f[j-a]和f[j]此时尚未被更新,相当于是f[i-1][j-a]与
f[i-1][j]
for j in range(s, a - 1, -1):
f[j] = min(f[j], f[j - a] + c)
# 遍历f[i]得到符合预算条件的最高攻击力
ans = 0
for i in range(s + 1):
if f[i] <= k:
ans = i
print(ans)</pre>
这道题暂未补解析。