简答题 偏难
#20645

武器购买 时间限制:1.0 s 内存限制:512.0 MB 题面描述 商店里有 n 个武器,第 i 个武器的强度为 p i ,花费为 c i 。 小杨想要购买一…

武器购买

时间限制: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

输出样例

3
-1
-1

对于全部数据,保证有 1≤t≤10,1≤n≤100,1≤pi,ci,P,Q≤5×104。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; #define ll long long ll dp[50010]; ll solve(int n, int P, int Q, vector&lt;pair&lt;int, int&gt;&gt;&amp; weapons) { dp[0] = 0; for (auto&amp; weapon : weapons) { int p = weapon.first; int c = weapon.second; for (int j = Q; j &gt;= c; --j) { if (dp[j - c]&gt;=0) { dp[j] = max(dp[j], dp[j - c] + p); } } } for (int j = 0; j &lt;= Q; ++j) { if (dp[j] &gt;= P) { return j; } } return -1; } int main() { int t; cin&gt;&gt;t; while(t--){ int n, P, Q; cin &gt;&gt; n &gt;&gt; P &gt;&gt; Q; memset(dp,-0x3f,sizeof dp); vector&lt;pair&lt;int, int&gt; &gt; weapons(n); for (int i = 0; i &lt; n; ++i) { cin &gt;&gt; weapons[i].first &gt;&gt; weapons[i].second; } cout &lt;&lt; solve(n, P, Q, weapons) &lt;&lt; "\n"; } return 0; }</pre>
这道题暂未补解析。