AcWing 1022. 宠物小精灵之收服__解法二
原题链接
简单
作者:
ChinaPie
,
2019-09-25 16:01:25
,
所有人可见
,
阅读 1453
参考了墨染空同学的解法二写的代码,时间复杂度O(M(K^2))
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010;
int V1;
int V2;
int f[N][N]; // f[i][j] 是得到精灵数为i体力值为j消耗的最少的精灵球数
int n, m, k;
int main()
{
scanf("%d%d%d",&n,&m,&k);
memset(f, 0x3f, sizeof f);
// 初始化, 精灵数为0消耗的精灵球数肯定为0
for(int i = 0; i <= m - 1; i ++)
f[0][i] = 0;
for(int i = 0; i < k; i ++)
{
cin >> V1 >> V2;
for(int j = k; j >= 1; j -- )
{
for(int g = m - 1; g >= V2; g --)
{
// 精灵球数必须在n之内
if(f[j - 1][g - V2] + V1 <= n)
f[j][g] = min(f[j][g], f[j - 1][g - V2] + V1);
}
}
}
// 最大精灵数
int res;
for(int i = k; i >= 0; i --)
if(f[i][m - 1] != INF)
{
res = i;
break;
}
// 剩余体力值
int ans = m - 1;
// 不同策略,只要精灵球数的消耗在n之内即可,不用和上一种方法一样需要相等才行
while(ans > 0 && f[res][ans - 1] <= n) ans --;
cout << res << " " << m - ans << endl;
// 这是解法一求剩余体力值的方法
// int res = m - 1;
// while(res > 0 && f[n][res - 1] == f[n][m - 1]) res --;
// cout << f[n][m - 1] << " " << m - res << endl;
return 0;
}