题目描述
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天,小智和皮卡丘来到了小精灵狩猎场,里面有很多珍贵的野生宠物小精灵。
小智也想收服其中的一些小精灵。
然而,野生的小精灵并不那么容易被收服。
对于每一个野生小精灵而言,小智可能需要使用很多个精灵球才能收服它,而在收服过程中,野生小精灵也会对皮卡丘造成一定的伤害(从而减少皮卡丘的体力)。
当皮卡丘的体力小于等于0时,小智就必须结束狩猎(因为他需要给皮卡丘疗伤),而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
当小智的精灵球用完时,狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择:收服它,或者离开它。
如果小智选择了收服,那么一定会扔出能够收服该小精灵的精灵球,而皮卡丘也一定会受到相应的伤害;如果选择离开它,那么小智不会损失精灵球,皮卡丘也不会损失体力。
小智的目标有两个:主要目标是收服尽可能多的野生小精灵;如果可以收服的小精灵数量一样,小智希望皮卡丘受到的伤害越小(剩余体力越大),因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力,已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。
请问,小智该如何选择收服哪些小精灵以达到他的目标呢?
样例
输入样例1:
10 100 5
7 10
2 40
2 50
1 20
4 20
输出样例1:
3 30
输入样例2:
10 100 5
8 110
12 10
20 10
5 200
1 110
输出样例2:
0 100
写三维的话会爆空间,所以只能跟01背包一样优化成把i这一维去掉
#include <iostream>
using namespace std;
const int N =1010, M = 510;
int f[N][M];
int main()
{
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < k; i ++ )
{
int v1, v2;
cin >> v1 >> v2;
for (int j = n; j >= v1; j -- )
for (int t = m - 1; t >= v2; t -- ) //将皮卡丘体力减少至零的小精灵是不收服的,所以体力从m-1开始枚举
f[j][t] = max(f[j][t], f[j - v1][t - v2] + 1);
}
cout << f[n][m - 1] << ' ';
int t = m - 1;
while (t > 0 && f[n][t - 1] == f[n][m - 1]) t -- ;
cout << m - t << endl;
}
Rita