简答题 偏难
#19809

道具商店 题目描述 道具商店里有 n 件道具可供挑选。第 i 件道具可为玩家提升a i 点攻击力,需要 c i 枚金币才能购买,每件道具只能购买一次。现在你有…

道具商店

题目描述

道具商店里有 n 件道具可供挑选。第 i 件道具可为玩家提升ai点攻击力,需要 ci 枚金币才能购买,每件道具只能购买一次。现在你有 k 枚金币,请问你最多可以提升多少点攻击力?

输入格式

第一行,两个正整数 n k ,表示道具数量以及你所拥有的金币数量。 接下来 n 行,每行两个正整数ai , ci ,表示道具所提升的攻击力点数,以及购买所需的金币数量。

输出格式

输出一行,一个整数,表示最多可以提升的攻击力点数。

样例

输入样例1 

3 11 99 1 33 2 11 3

输出样例1 

132

输入样例2 

4 100 10 1 20 11 100 99 40 33

输出样例2 

110

数据范围

对于部分测试点,保证 1 ≤k ≤500, 1 ≤ ci  ≤500

对于所有测试点,保证 1 ≤n ≤500 , 1 ≤k ≤10^9 , 1 ≤ ai ≤500 , 1 ≤ ci  ≤10^9

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; const int N = 505; const int oo = 1e9 + 10; int n, k; int f[N * N]; int main() {     scanf("%d%d", &amp;n, &amp;k);     for (int i = 1; i &lt; N * N; i++)         f[i] = oo;     f[0] = 0;     int s = 0;     for (int i = 1; i &lt;= n; i++) {         int a, c;         scanf("%d%d", &amp;a, &amp;c);         s += a;         for (int j = s; j &gt;= a; j--)             f[j] = min(f[j], f[j - a] + c);     }     int ans = 0;     for (int i = 0; i &lt; N * N; i++)         if (f[i] &lt;= k)             ans = i;     printf("%d\n", ans);     return 0; }</pre>
这道题暂未补解析。