用DP計算max value

我在解關於DP的問題上遇到一些困難,想請教大家

以下為題目原文:


There are n types of ways, each represented by (ai, bi, ki) for 1 ≤ i ≤ n, where ai ≥ 1 and bi ≥ 1. If the i-th formula is applied at the start of a round, the gold’s length immediately increases by ai. Subsequently, for the next ki rounds, including the round of formula usage, the gold’s length decreases by bi at the end of each round. The effects of the formulas can accumulate. Thus, at the conclusion of each round, the decrease in gold length is equal to the sum of bi for all formulas i that remain in effect.

In each round, we can use at most one formula, and each formula can only be used once. It is free to choose any subset of formulas and use them in any desired order. Initially, the gold length is 0.

(a) Suppose that n = 4 and the formulas are  (1, 2, 1), (2, 3, 1), and (3, 5, 1) Find the maximum length of the gold

(b) Define the following notations: • A(i, j) represents the maximum length of the gold under the following conditions: (1) Only the first i formulas are taken into account (2) j formulas, including the i-th formula, are in effect when the value A(i, j) is achieved.

• B(i, j) represents the maximum length of the gold under the following conditions: (1) Only the first i formulas are taken into account (2) j formulas, including the i-th formula, are in effect when the value B(i, j) is achieved (3) the i-th formula is used in the first round.

A(i, j) and B(i, j) are defined to be −∞ if it is not possible. Based on the optimal substructure, write down the recurrence formula of A(i, j) and B(i, j). If needed, you can assume that the formulas are sorted in a particular order.

----------------------------
不理解的部分:
不懂他每一輪得值是怎麼計算的,以採取兩輪第一輪:formula 1 ,第二輪用formula 2為例
1st: +5
2nd: +20 -3
最終: 5+20-3=22
這樣的理解是對的嗎?

理解对了。

逻辑是:
首先定义了一种“公式”或“配方”,每种公式由三个参数 (ai, bi, ki) 定义。当在一轮开始时使用第 i 种公式时,金子的长度立即增加 ai。然后,在接下来的 ki 轮中,包括使用公式的那一轮在内,每轮结束时,金子的长度都会减少 bi。这些公式的效果可以累积,所以在每一轮结束时,金子长度的减少量等于所有仍在生效的公式的 bi 之和。


如果有帮助,请点击一下采纳该答案~谢谢