概览
小智, 皮卡丘
小精灵, 精灵球个数, 皮卡丘的伤害
皮卡丘体力<=0, 伤害的也不能收
用完精灵球
- 收服尽可能多的精灵
- 精灵数相同时候,伤害最小
题解
花费1:精灵球数量 N
花费2:皮卡丘体力值 M
价值:小精灵的数量 K
f[i,j,k]表示所有只从前i个物品中选,且花费1不超过j,花费2不超过k的选法的最大价值
老是想着01背包,却没有跳出来从DP的角度直接开始建模问题。问题扩展了,多一维不就可以了吗
f[i,j,k] = max(f[i-1, j, k], f[i-1, j-v1[i], k-v2[i] + 1)
nb!! 注意这里有限制
问:
最多收服的小精灵数 f[K, N, M]
最少耗费体力 f[K, N, m] == f[K, N, M]
真的妙,求数量就这样一下就转化了
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = 510;
int n, V1, V2;
int f[N][M];
int main() {
cin >> V1 >> V2 >> n;
for (int i = 0; i < n; i ++) {
int v1, v2;
cin >> v1 >> v2;
for (int j = V1; j >= v1; j --)
for (int k = V2 - 1; k >= v2; k --)
// 注意体力小于等于0,包括等于0时,小精灵就不会被收服
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;
}