题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
c++ 没有办法直接定义三维数组 所以从实现角度上 没办法使用朴素算法了
因为直接使用优化后的代码 但是可以自己先写一个三维版的朴素算法hh
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
// 只能采用 优化版本
const int N = 1e3+10;
int f[510][1010];
int v[N]; // 需要精灵球的数量
int w[N]; // 所造成的伤害
int main()
{
int n, m, r; //精灵球数量 体力值 野生数量
cin>>n>>m>>r;
for(int i = 1; i <= r; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= r; i++)
for(int j = m - 1; j >= w[i]; j--)
for(int k = n; k >= v[i]; k--)
{//利用滚动数组 直接省去 f[i]
// 因为皮卡丘的体力不能为0 因此 j 就需要从 m - 1开始遍历 // // // 按照y总说的 如果按照m开始的话 也就是不超过m即可 但是按照题意 当体力为0 时候 狩猎结束
f[j][k] = max(f[j][k], f[j-w[i]][k - v[i]] + 1);
}
cout<<f[m-1][n]<<" ";
int cost_min_health = m;
// 遍历以下 找到用的最小体力 这里只需 让体力逐步遍历即可 n保持不变
// 精灵球个数不变
for(int i = 0; i <= m - 1; i++)
{
if(f[i][n] == f[m-1][n])
cost_min_health = min(cost_min_health, i);
}
cout<<m - cost_min_health<<endl;
return 0;
}