宠物小精灵之收服

dp 二维dp 01背包

题目

小智收服小精灵, 对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。

当皮卡丘的体力小于等于 00 时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于 00 的野生小精灵也不会被小智收服。

当小智的精灵球用完时，狩猎也宣告结束。

主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。

输入数据的第一行包含三个整数：N(0 < N < 1000)，M(0 < M < 500)，K(0 < K < 100)，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。

之后的 K 行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出为一行，包含两个整数：C，R，分别表示最多收服 C 个小精灵，以及收服 C 个小精灵时皮卡丘的剩余体力值最多为 R。

10 100 5
7 10
2 40
2 50
1 20
4 20

3 30

思路

两个价值, 一个代价, 经典二维dp。

状态表示：f[k][i][j] 收服到前k个小精灵, 当前用了i个精灵球, 皮卡丘体力为j 状态计算：

• f[k - 1][i][j] 不选收服当前小精灵
• f[k - 1][i - v1][j - v2] 收服当前小精灵

初始化： f[0][N][M] = 0

注意枚举时不能从体力为0转移。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10, M = 5e2 + 10, K = 1e2 + 10;
int f[N][M];
int n,m,k;
int v1[N],v2[N];
 
 
int main()
{
    cin >> m >> k >> n;
    for(int i = 1; i <= n; i++) cin >> v1[i] >> v2[i];
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >= v1[i]; j--)
            for(int q = k; q >= v2[i]; q--)
            {
                    f[j][q] = max(f[j][q], f[j - v1[i]][q - v2[i]] + 1);
                
            }
    }
    
    for(int i = 0; i < k; i++)
        if(f[m][i] == f[m][k-1])
        {
            cout << f[m][k-1] << " " << k - i << endl;
            break;
        }
    return 0;
}