本文介绍: 信息学奥赛一本通 1292:宠物小精灵之收服

算法分析

问题二维费用背包。精灵球数量、皮卡丘体力值都是费用

题目说,如果一个野生小精灵皮卡丘体力小于等于0,那么无法收服该小精灵。也就是说当皮卡丘m体力时,最多可以消耗的体力m-1点。在输入m后,先让m–,此时m表示最多可以消耗的体力值。

1. 状态定义

状态定义:dp[i][j][k]:在前i个野生小精灵选择小精灵捕捉,最多使用j个精灵球,以及k皮卡丘体力值,能捕捉到的最多的小精灵的数量。

2. 状态转移方程

记:b[i]:收第i小精灵需要的精灵球数, d[i]:收服第i小精灵皮卡丘损失体力

子集1:如果捕捉第i小精灵,接下来需要在前i-1个小精灵中选择小精灵,最多使用j-b[i]个精灵球,皮卡丘最多消耗kd[i]点体力值,在这种情况下能够捕捉到的小精灵数量最多为dp[i-1][j-b[i]][kd[i]],加上刚刚捉到的1只,所以dp[i][j][k] = dp[i-1][j-b[i]][kd[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)。

4. 复杂度优化

根据该题的描述,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 &gt;> 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进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注