P1782 旅行商的背包

pingter2024年10月25日大约 3 分钟

P1782 旅行商的背包

题目描述

小 S 坚信任何问题都可以在多项式时间内解决，于是他准备亲自去当一回旅行商。在出发之前，他购进了一些物品。这些物品共有 $n$ 种，第 $i$ 种体积为 $V_{i}$ ，价值为 $W_{i}$ ，共有 $D_{i}$ 件。他的背包体积是 $C$ 。怎样装才能获得尽量多的收益呢？作为一名大神犇，他轻而易举的解决了这个问题。

然而，就在他出发前，他又收到了一批奇货。这些货共有 $m$ 件，第 $i$ 件的价值 $Y_{i}$ 与分配的体积 $X_{i}$ 之间的关系为： $Y_{i} = a_{i} X_{i}^{2} + b_{i} X_{i} + c_{i}$ 。这是件好事，但小 S 却不知道怎么处理了，于是他找到了一位超级神犇（也就是你），请你帮他解决这个问题。

输入格式

第一行三个数 $n, m, C$ ，如题中所述；

以下 $n$ 行，每行有三个数 $V_{i}, W_{i}, D_{i}$ ，如题中所述；

以下 $m$ 行，每行有三个数 $a_{i}, b_{i}, c_{i}$ ，如题中所述。

x_x AC，WA，TLE五颜六色

看了下AC的大佬说这个卡时间很紧，max和deque之类的都会拖后腿，另外这题可能单调队列跑不过二进制

下面换二进制试试

改成二进制AC了

题解

#include <iostream>
#include <deque>
#include <cstring>

#define debug(x) #x << ":" << x << " "
#define ll long long
using namespace std;

ll dp[2][12800];
int now = 0;

struct
{
    ll v; // 体积
    ll w; // 价值
    ll d; // 数量
} goods[12800];

struct
{
    ll a, b, c;
} odd[16];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, C;
    cin >> n >> m >> C;
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < n; i++)
    {
        cin >> goods[i].v >> goods[i].w >> goods[i].d;
    }
    for (int i = 0; i < m; i++)
    {
        cin >> odd[i].a >> odd[i].b >> odd[i].c;
    }

    // 二进制优化
    for (int i = 0; i < n; i++)
    {

        int s = goods[i].d;
        for (int c = 1; s >= c; s -= c, c <<= 1)
        {
            int now_v = goods[i].v * c;
            int now_w = goods[i].w * c;

            for (int j = C; j >= now_v; j--)
            {
                dp[now][j] = max(dp[now][j], dp[now][j - now_v] + now_w);
            }
        }
        if (s != 0)
        {
            int now_v = goods[i].v * s;
            int now_w = goods[i].w * s;

            for (int j = C; j >= now_v; j--)
            {
                dp[now][j] = max(dp[now][j], dp[now][j - now_v] + now_w);
            }
        }
    }

    for (int i = 0; i < m; i++)
    {
        int pre = now;
        now = 1 - now;

        for (int j = 0; j <= C; j++)
        {
            dp[now][j] = dp[pre][j];
            for (int x = 0; x <= j; x++) // 即使x = 0，也有c，所以x为0也要考虑
            {
                dp[now][j] = max(dp[now][j], dp[pre][j - x] + odd[i].a * x * x + odd[i].b * x + odd[i].c);
            }
        }
    }

    cout << dp[now][C];

    return 0;
}

P1782 旅行商的背包

P1782 旅行商的背包

题目描述

输入格式

输出格式

说明/提示

样例解释

限制与约定

思路

题解