P1616 疯狂的采药

pingter2024年10月5日大约 4 分钟

P1616 疯狂的采药

题目背景

此题为纪念 LiYuxiang 而生。

题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

$1$ . 每种草药可以无限制地疯狂采摘。

$2$ . 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

对于 $30 %$ 的数据，保证 $m \leq 10^{3}$ 。
对于 $100 %$ 的数据，保证 $1 \leq m \leq 10^{4}$ ， $1 \leq t \leq 10^{7}$ ，且 $1 \leq m \times t \leq 10^{7}$ ， $1 \leq a_{i}, b_{i} \leq 10^{4}$ 。

思路

完全背包模板

struct herb
{
    long long time;
    long long value;
};

herb herbs[10240];

long long dp[2][10000020];

没想到直接MLE了x_x

# 简单算一下
128M=131072KB=134217728B
=char[134217728]
=int[33554432]
=long long[16777216]

所以这里超了,换int试试

最后两个测试点TLE了,继续考虑一下怎么优化

没找到方法,下载了测试数据,发现: 3794898 1 6041 3102

居然这么离谱的输入做一下优化,种类较少的时候用最大公因数来遍历

#include <iostream>
#include <cstring>
#include <algorithm>
#define debug(x) #x << ": " << x << " "
using namespace std;

struct herb
{
    int time;
    int value;
};

herb herbs[10240];

int dp[2][10000020];
int now = 0;

int gcd(int a, int b)
{
    while (b != 0)
    {
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    memset(dp, 0, sizeof(dp));
    int t, m;
    cin >> t >> m;

    for (int i = 1; i <= m; i++)
    {
        cin >> herbs[i].time >> herbs[i].value;
    }

    int gcd_num = herbs[1].time;
    for (int i = 2; i <= m && gcd_num > 1; i++)
    {
        gcd_num = gcd(gcd_num, herbs[i].time);
    }
    // cout << debug(gcd_num);

    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j <= t; j += gcd_num)
        {
            int pre = now;
            now = 1 - now;
            // dp[now][j] = dp[pre][j];
            for (int k = 0; k * herbs[i].time <= j; k++)
            {
                dp[now][j] = max(dp[now][j], dp[pre][j - k * herbs[i].time] + k * herbs[i].value);
                // if (i == 3)
                // {
                    // cout << debug(i) << debug(j) << debug(k) << debug(dp[now][j]) << "\n";
                // }
            }
        }
    }

    cout << dp[now][t - (t % gcd_num)];

    return 0;
}

能过一个了,还剩一个 10000000 1 1 10000 离谱

这时突然发现,这个完全背包写的不对......

    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j <= t; j += gcd_num)
        {
            int pre = now;
            now = 1 - now;
            for (int k = 0; k * herbs[i].time <= j; k++)
            {
                dp[now][j] = max(dp[now][j], dp[pre][j - k * herbs[i].time] + k * herbs[i].value);
            }
        }
    }

这里总共三层循环,物品,容量,当前物品购买数量,但是其实容量已经约束了能买的物品数量了,不需要额外多一层循环,而且由于物品是无限的,也不需要滚动数组,可以只用一个

题解

#include <iostream>
#include <cstring>
#include <algorithm>
#define debug(x) #x << ": " << x << " "
using namespace std;

struct herb
{
    long long time;
    long long value;
};

herb herbs[10240];

// int dp[2][10000020];
long long dp[10000020];

int gcd(int a, int b)
{
    while (b != 0)
    {
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    memset(dp, 0, sizeof(dp));
    int t, m;
    cin >> t >> m;

    for (int i = 1; i <= m; i++)
    {
        cin >> herbs[i].time >> herbs[i].value;
    }

    // int gcd_num = herbs[1].time;
    // for (int i = 2; i <= m && gcd_num > 1; i++)
    // {
    //     gcd_num = gcd(gcd_num, herbs[i].time);
    // }
    int gcd_num = 1;
    // cout << debug(gcd_num);

    for (int i = 1; i <= m; i++)
    {
        for (int j = herbs[i].time; j <= t; j += gcd_num)
        {

            dp[j] = max(dp[j], dp[j - herbs[i].time] + herbs[i].value);

            // 都不需要
            // for (int k = 0; k * herbs[i].time <= j; k++)
            // {
            //     // dp[now][j] = max(dp[now][j], dp[pre][j - k * herbs[i].time] + k * herbs[i].value);
            //     // if (i == 3)
            //     // {
            //         // cout << debug(i) << debug(j) << debug(k) << debug(dp[now][j]) << "\n";
            //     // }
            // }
        }
    }

    cout << dp[t - (t % gcd_num)];

    return 0;
}

P1616 疯狂的采药

P1616 疯狂的采药

题目背景

题目描述

输入格式

输出格式

提示

数据规模与约定

思路

题解