简答题 偏难
#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] &lt;= k: ans = i print(ans)</pre>
这道题暂未补解析。