题目大意：
一共会遇到 n 个 野生宝可梦，小智有 m 个 精灵球，皮神有 t 滴 血
对于每个 野生宝可梦 来说，如果要捕捉他，需要 $v1_i$ 个 精灵球，战斗后皮神要掉 $v2_i$ 滴 血
如果皮神 血量 ≤0，则小智停止狩猎
小智对于每个 野生宝可梦 要么收服，要么逃跑
求一种方案：收服 尽可能多 的 野生宝可梦 ；如果收服数量一样，要皮神 血量最多
输出该方案的 野生宝可梦 收服数量，以及皮神战斗结束后的 剩余血量
-彩色铅笔
解题思路：
既然每收服一个精灵就需要精灵球和血量，那就是一个二维费用的背包问题了。
$$闫氏DP分析法$$
- 状态表示——集合：$f[i][j][k]$ 表示考虑前 $i$ 个精灵，且精灵球不超过 $j$个 ，且已使用皮神血量 $k$ 滴的集合下能获得的最大收服数。
- 状态表示——属性：因为是求最大收服数，故为 $max$。
- 状态计算——集合划分：考虑第 $i$ 个是否收服。
- 不收服或收服不了（剩余血量或精灵球数不够）：$f[i - 1][j][k]$。
- 选：$f[i - 1][j - v1_i][k - v2_i] + 1$。首先你对第 $i$ 个物品进行了你的抉择，所以前一维变成了 $i - 1$，接着因为使用了 $v1_i$ 的精灵球数，所以应该是 $j - v1_i$，还花费了 $v2_i$ 的血量，所以是 $k - v2_i$，最后你把它收服了，所以要$+1$。
当然了，也可以优化成一维来做。
还有一种写的方法就是把f[i][j][k]的表示变成：考虑前 $i$ 个精灵，且精灵球不超过 $j$个 ，收服小精灵数为 $k$ 个 的花费的血量，同样也可以变成：考虑前 $i$ 个精灵，且血量不超过 $j$ ，收服小精灵数为 $k$ 个 的花费的精灵球数，同样是可以的，代码就不贴了，时间复杂度一个是 $O(nmk)$ 一个是 $O(k^2m)$。
完整代码，时间复杂度：$O(nmk)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int V1, V2, n;
int f[N * 2][N];
int main()
{
cin >> V1 >> V2 >> n;
for (int i = 1; i <= n; i ++ ) {
int v1, v2;
cin >> v1 >> v2;
for (int j = V1; j >= v1; j -- ) {
for (int k = V2 - 1; k >= v2; k -- ) {
f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
}
}
}
cout << f[V1][V2 - 1] << " ";
int k = V2 - 1;
while (k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k --;
cout << V2 - k << endl; //还要输出收服最多的时候剩余血量最大值
return 0;
}
？？？宝可梦？？？
终于找到一个懂宝可梦的人了
反应迟钝的我
肯定是被泥巴鱼洗脑了点个赞行不行qwq
复杂度一个是 $O(nmk)$ 一个是 $O(k^2m)$ 吧
写的快了写错了，谢谢提醒
这句话是什么意思 while (k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k –;
找到满足最大价值的所有状态里，第二维费用消耗最少的
这很简单，认真想想就知道了
哦哦，懂了，蟹蟹你吖
请问是k越小越好，所以在确定收服最大的值时通过尝试k-1让k变小1是否还是等于收服最大值如果等于，就让k – ，k最小是0所以第一个条件k > 0.
我为啥看不懂你在说啥，语文不好.jpg
反正就是你要让你花费的最小，还要你能得到的最多，就是这个意思
是我表达不清晰hh
因为k越小越好，在确定f[V1][V2 - 1]的时候，通过尝试让k不断减一（达到让k不断减小的目的）检查f[V1][k - 1]是否等于f[V1][V2 - 1]，这是条件二的解释
第一个条件不能是k>=0因为k如果等于0条件二成立那么k – k就是-1了，所以k只能是>0
目的是明白的，主要想搞清循环条件的逻辑
第一个条件就是有可能有些东西都不需要代价，所以防止<0，你说的大体是对的。
有点纳闷这个k-1 不懂
#include[HTML_REMOVED]
using namespace std;
int f[1005][505];//消耗 j个球 k滴血
int main(){
int n,m,x;scanf(“%d%d%d”,&n,&m,&x);
int v1,v2;
for(int i=1;i<=x;i++){
cin>>v1>>v2;
for(int j=n;j>=v1;j–){
for(int k=m;k>=v2;k–){
f[j][k]=max(f[j][k],f[j-v1][k-v2]+1);
}
}
}
cout<[HTML_REMOVED]0&&f[n][k-1]==f[n][m-1])k–;
cout<<m-k;
return 0;
}
为啥是k-1与m-1比较 不是k与m-1比较
代码加markdown谢谢…
为啥是f[n][k-1]==f[n][m-1] 而不是f[n][k]==f[n][m-1]