P16891 [GKS 2022 #F] Story of Seasons

你是一位超级农夫，拥有一些蔬菜种子和一片无限大的农场。事实上，你不仅是一位农夫，还秘密地是一位超级程序员！作为一名超级程序员，你希望利用你的编程技能最大化农场的利润。 由于你每天的精力有限，每天最多可以种植 $X$ 颗种子。起初，你有 $N$ 种蔬菜种子。第 $i$ 种蔬菜的种子数量为 $Q_i$，并且该种蔬菜的每颗种子从种植之日起需要 $L_i$ 天才能成熟。一旦成熟，你可以将其卖出获得 $V_i$ 美元。假设收获和销售蔬菜不消耗精力或时间。此外，你的农场无限大，因此生长的蔬菜不会互相挤占。 请注意，尽管你的农场面积无限，但你能种植种子的天数却是有限的。暖季只持续 $D$ 天，之后严酷的冬季到来。任何尚未成熟的蔬菜会立即死亡，无法转化为利润。未种植的剩余种子也无法转化为利润。 作为超级农夫和超级程序员，你想出一个完美的种植计划来最大化你的利润。请计算你将获得的总利润。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含三个整数 $D$、$N$ 和 $X$：分别表示暖季的天数、初始拥有的蔬菜种子种类数，以及每天最多可以种植的种子数量。 接下来的 $N$ 行描述每种种子。第 $i$ 行包含三个整数 $Q_i$、$L_i$ 和 $V_i$：分别表示该种蔬菜的种子数量、所需成熟天数，以及每株成熟作物的价值。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是通过优化种植计划能获得的最大金额。

在样例 #1 中，有 $D = 5$ 天，$N = 4$ 种蔬菜，每天最多种植 $X = 1$ 颗种子。假设这 $4$ 种蔬菜分别是菠菜、南瓜、胡萝卜和卷心菜，我们有： - 菠菜需要 $2$ 天生长，每株价值 $3$ 美元，初始有 $1$ 颗菠菜种子。 - 南瓜需要 $3$ 天生长，每株价值 $10$ 美元，初始有 $1$ 颗南瓜种子。 - 胡萝卜需要 $4$ 天生长，每株价值 $5$ 美元，初始有 $1$ 颗胡萝卜种子。 - 卷心菜需要 $2$ 天生长，每株价值 $2$ 美元，初始有 $1$ 颗卷心菜种子。 你能获得的最大利润为 $18$ 美元。你可以使用以下种植计划： - 第 $1$ 天：种植 $1$ 颗胡萝卜 - 第 $2$ 天：种植 $1$ 颗南瓜 - 第 $3$ 天：种植 $1$ 颗菠菜 - 第 $4$ 天：种植 $1$ 颗卷心菜 - 第 $5$ 天：什么都不做 按照该计划，蔬菜成熟并转化为利润的情况如下： - 第 $1$ 天：无收获 - 第 $2$ 天：无收获 - 第 $3$ 天：无收获 - 第 $4$ 天：无收获 - 第 $5$ 天：收获 $1$ 株菠菜、$1$ 株南瓜和 $1$ 株胡萝卜，赚得 $18$ 美元 注意，卷心菜本应在第 $6$ 天成熟，但由于冬季到来实际上会死亡。 在附加样例 #1 中，有 $D = 5$ 天，$N = 3$ 种蔬菜，每天最多种植 $X = 4$ 颗种子。假设这 $3$ 种蔬菜分别是菠菜、南瓜和胡萝卜，我们有： - 菠菜需要 $2$ 天生长，每株价值 $3$ 美元，初始有 $5$ 颗菠菜种子。 - 南瓜需要 $3$ 天生长，每株价值 $10$ 美元，初始有 $2$ 颗南瓜种子。 - 胡萝卜需要 $4$ 天生长，每株价值 $5$ 美元，初始有 $2$ 颗胡萝卜种子。 你能获得的最大利润为 $45$ 美元。你可以使用以下种植计划： - 第 $1$ 天：种植 $1$ 颗南瓜、$2$ 颗胡萝卜和 $1$ 颗菠菜 - 第 $2$ 天：种植 $2$ 颗菠菜和 $1$ 颗南瓜 - 第 $3$ 天：种植 $2$ 颗菠菜 - 第 $4$ 天：什么都不做 - 第 $5$ 天：什么都不做 按照该计划，蔬菜成熟并转化为利润的情况如下： - 第 $1$ 天：无收获 - 第 $2$ 天：无收获 - 第 $3$ 天：收获 $1$ 株菠菜，赚得 $3$ 美元 - 第 $4$ 天：收获 $2$ 株菠菜和 $1$ 株南瓜，赚得 $16$ 美元 - 第 $5$ 天：收获 $2$ 株菠菜、$1$ 株南瓜和 $2$ 株胡萝卜，赚得 $26$ 美元 ### 限制条件 内存限制：$1$ GB。 $1 \le T \le 100$。 对于所有 $i$，$1 \le V_i \le 10^6$。 对于所有 $i$，$1 \le L_i \le D$。 **测试集 1** $2 \le D \le 1000$。 $1 \le N \le 15$。 $X = 1$。 对于所有 $i$，$Q_i = 1$。 **测试集 2** $2 \le D \le 10^5$。 $1 \le N \le 10^5$。 $1 \le X \le 10^9$。 对于所有 $i$，$1 \le Q_i \le 10^6$。 **测试集 3** $2 \le D \le 10^{12}$。 $1 \le N \le 10^5$。 $1 \le X \le 10^9$。 对于所有 $i$，$1 \le Q_i \le 10^6$。 $D \times X \le 10^{18}$。 翻译由 DeepSeek V4 Pro 完成