题目描述

现需上市 $n$ 赛斯重量的赛斯石，卖家想算出这些赛斯石经过某种合并方式来获得的最大收益。然而目前有一个问题，市场在真程大殿附近 (真程海洋中心位置)，卖家需要租船送赛斯石过去 (即不考虑卖家自己租船过去的费用)，目前有 $10$ 种船可以租，载重量从 $1 \si$ 到 $10 \si$，每艘船的租价也是有所不同的，如下表所示：

由于真程大殿附近有强烈的赛斯力，导致无法对赛斯石进行任何操作，商家将赛斯石运过来之后就只能按照之前合并好的卖。假设卖家不返回，且这些赛斯石全部能卖出去。现在卖家他要计算总盈利 (设总盈利 = 赛斯石的总收益 - 租船所需总费用)，请你设计一个程序，算出一种最佳方案，以获得最大总盈利。

输入格式

第一行包含一个正整数 $n$ ($n < 10^5$)，表示赛斯石的总量 (单位：$\si$)。

第二行包含 $10$ 个正整数 $a_1, a_2, \cdots, a_{10}$ ($a_i < 10^5$)，分别为 $1 \si$ 到 $10 \si$ 的赛斯石市场价格 (单位：元)。

输出格式

输出一行一个整数，表示最大总盈利。

题解

看起来像个裸的背包 DP，不过有可能会在船上进行分割，因此需要增加一个预处理。

显然，每艘船必须是要放满的，否则可以使用更轻的船。

记 $b_i$ 为使用大小为 $i$ 的船的赛斯石收益 (不包括租船费用)的最大值，那么有非常 simple 的转移方程：

$$ b_i = \max \left\{ a_i, \max_{1 \leq j < i} \{ b_{i-j} + b_j \} \right\} $$

那么算上租船费用，租大小为 $i$ 的船的净收益为 $b_i - g_i$，其中 $g_i$ 为船的租价，见上表。

然后再跑一个大的背包 DP，记 $f_{i, j}$ 表示只租大小为 $1 \sim i$ 的船，一共运了 $j \si$ 的赛斯石所能获得的最大净收益，则

$$ f_{i, j} = \max \{f_{i-1, j}, (f_{i, j-i} + b_i)[j \geq i]\} $$

最终答案即 $f_{10, n}$，$f$ 的第一维 ($i$) 可以压缩掉，时间复杂度 $O(w \cdot n)$，其中 $w$ 为船的最大载重 (也是最大可以卖的赛斯石重)，本题中为 $10$。

代码

#include <bits/stdc++.h>
#define N 100034
using namespace std;

typedef long long ll;

const int _[11] = {0, 1, 3, 5, 7, 9, 10, 11, 14, 15, 17};

int n, i, j;
int a[11];
ll f[N];

template <typename T>
inline void up(T &x, const T y) {x < y ? x = y : 0;}

int main(){
    scanf("%d", &n);
    for(i = 1; i <= 10; ++i) scanf("%d", a + i);
    for(i = 2; i <= 10; ++i)
        for(j = 1; j < i; ++j)
            up(a[i], a[i - j] + a[j]);
    for(i = 1; i <= 10; ++i) a[i] -= _[i];
    memset(f, 192, sizeof f);
    f[0] = 0;
    for(i = 1; i <= 10; ++i)
        for(j = i; j <= n; ++j)
            up(f[j], f[j - i] + (ll)a[i]);
    printf("%lld\n", f[n]);
    return 0;
}

坑

坑1：需要注意的是，$j \si$ 的赛斯石不一定是只装在 $j \si$ 的船上才收益最大，可能是和其它赛斯石共同装在一个船上，故第一个 DP 必不可少。

坑2：其次是开 long long。