← 返回题单

题单练习资源分配型DP入门

← 上一题下一题 →

A6985 | $赛斯石$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

题目背景 “白露横江，水光接天，纵一苇之所如，凌万顷之茫然。” —— 苏轼 真程海洋近来需要进购大批赛斯石。首先我们来了解一下赛斯，赛斯是一个重量单位，我们用 $si$ 作为其单位（例如 $1$ 赛斯就是 $1si$）。 赛斯石具有特殊的性质：它原本以 $1si$ 的单体存在，但经过自然枪精化后，可以与其他精化过的赛斯石合并。合并到合适的重量后，将其钝化即可定型。如果合并不当，也可以用金刚刀将其切开（只能切成整数赛斯重量）。不同重量的赛斯石在市场上的价格是不同的。 题目描述 现需上市 $N$ 赛斯重量的赛斯石，卖家希望计算出通过某种合并和运输方案能获得的最大 总盈利 。 市场位于真程海洋中心（真程大殿附近），卖家需要租船将赛斯石运送过去。目前有 $10$ 种船可供租赁，载重量从 $1si$ 到 $10si$ 不等，每种船的租金如下表所示： 载重 ($si$) 12345678910 租金 (元) 135791011141517 由于真程大殿附近存在强烈的赛斯力场， 赛斯石运抵后无法进行任何合并或切割操作 ，只能按照运送前的状态出售。 假设卖家不考虑返程费用，且所有运送的赛斯石均能售出。 总盈利 = 赛斯石的总收益 - 租船所需总费用 。 请你设计一个程序，计算最大总盈利。

输入格式

输入共两行。 第一行包含一个整数 $N$，表示需要上市的赛斯石总量（单位：$si$）。 第二行包含 $10$ 个整数 $a_1, a_2, \dots, a_{10}$，分别表示重量为 $1si$ 到 $10si$ 的赛斯石在市场上的单价（单位：元）。

输出格式

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

输入输出样例

输入 #1

11
1 6 11 17 23 27 33 35 38 43

输出 #1

输入 #2

7
1 5 14 18 20 28 31 34 39 42

输出 #2

C++ 编辑器

输入

输出