题目说,如果一个野生小精灵让皮卡丘的体力小于等于0,那么无法收服该小精灵。也就是说当皮卡丘有m点体力时,最多可以消耗的体力为m-1点。在输入m后,先让m–,此时m表示最多可以消耗的体力值。
状态定义:dp[i][j][k]:在前i个野生小精灵中选择小精灵捕捉,最多使用j个精灵球,以及k点皮卡丘的体力值,能捕捉到的最多的小精灵的数量。
记:b[i]:收第i小精灵需要的精灵球数, d[i]:收服第i小精灵皮卡丘损失的体力值
子集1:如果捕捉第i小精灵,接下来需要在前i-1个小精灵中选择小精灵,最多使用j-b[i]个精灵球,皮卡丘最多消耗k–d[i]点体力值,在这种情况下能够捕捉到的小精灵数量最多为dp[i-1][j-b[i]][k–d[i]],加上刚刚捉到的1只,所以dp[i][j][k] = dp[i-1][j-b[i]][k–d[i]]+1
子集2:如果不捕捉第i小精灵,接下来需要在前i-1个野生小精灵中选择,最多使用j个精灵球,以及k点皮卡丘的体力值,可以捕捉到的小精灵数量最多为dp[i][j][k] = dp[i-1][j][k]
以上两种情况取最大值
3. 获取剩余体力
第二个问要求的是,在收服最多小精灵的前提下,皮卡丘可以剩余的最多体力。
假设最多有n个精灵球,皮卡丘最多可以消耗m点体力(这是m–后的m,实际总体力值为m+1),一共有ka个野生小精灵。那么在所有野生小精灵中,选择要捕获的小精灵,最多消耗n个精灵球和m点皮卡丘的体力,能获得的最多的小精灵的数量为dp[ka][n][m]。如果不消耗m点体力,而是消耗k点皮卡丘的体力(0 ≤ k ≤ m 0le k le m0≤k≤m),看在捕获的小精灵数量相同的情况下,k最小可以是几。也就是说,在所有小精灵中选择小精灵捕获,消耗n个精灵球,要捕获数量为dp[ka][n][m]的小精灵,皮卡丘最少消耗的体力可以是多少。
k从0遍历到m,如果dp[ka][n][k] == dp[ka][n][m],那么最少消耗k点体力,就可以捕获到最多的小精灵。剩下的体力值应该为m+1-k(因为m是最多可以消耗的体力值,总体力值实际为m+1)。
根据该题的描述,dp[i][j][k]第1维是小精灵数量,最大100;第2维是精灵球个数,最大1000;第3维是皮卡丘体力值,最大500。乘在一起为这个三维数组的最大变量数,为5 ∗ 1 0^7,内存空间限制为65535KB,65535 ∗ 1024 / 4 = 16776960,最多可以保存约1.67 ∗ 1 0^7 个int类型的变量。如果直接声明三维数组使用,一定会内存超限。因此对于该题,必须做滚动数组优化,去掉表示前几个小精灵的第一维。
#include <bits/stdc++.h>
using namespace std;
int dp[1005][505];//dp[i][j][k]:(第一维i被优化掉)前i个野生小精灵中最多使用j个精灵球,k点皮卡丘的体力值,能捕捉到的最大小精灵数量。
int b[105], d[105];//b[i]:收第i小精灵需要的精灵球球数 d[i]:收第i小精灵皮卡丘损失的体力值
int main()
{
int n, m, ka, r;
cin >> n >> m >> ka;//n个精灵球 皮卡丘m点体力值 野生小精灵有ka个
m--;//不能把m点体力值都用完,最多可以使用m-1点体力
for(int i = 1; i <= ka; ++i)
cin >> b[i] >> d[i];
for(int i = 1; i <= ka; ++i)
for(int j = n; j >= b[i]; --j)
for(int k = m; k >= d[i]; --k)
dp[j][k] = max(dp[j][k], dp[j-b[i]][k-d[i]]+1);
for(int k = 0; k <= m; ++k)//用掉的体力值可以为0,从0开始遍历
{
if(dp[n][k] == dp[n][m])
{
r = m + 1 - k ;//原总体力值为m+1,减去用掉的体力j
break;
}
}
cout << dp[n][m] << ' ' << r;
return 0;
}
原文地址:https://blog.csdn.net/pheatonhb/article/details/134671457
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_43974.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!