背景

image-20251127145356350

我估计一眼大家就知道这次内容是要说什么了

这种层出不穷的抽象小游戏中，往往有一大类就是，通过走不同的门，然后使得你的人数始终比对面多

广告里面的弱智操作常常看得人血压飙升，再加上广告中充满挑衅智商意味的台词来激发用户的纠正欲，就很容易让人点进去被感觉智商被羞辱一番的感受后退出，此时你大概率还在厕所

问题分析

问题抽象

我们把问题给抽象出来，以一个相对清晰严谨的情况说明，这是一种路径选择下的数值增益优化问题

一开始，我们拥有一个小人1个（其实这个初始数值可以是任何数，但是在不是1的情况下真的会不太一样），场地上一共两个路径，而且每条路径中存在多个路径选项，每个选项对应不同的数值增益 / 倍率。一回合设为你前进一次，经过某条路径上的一个条件，每回合只有在经过一条路径上的一个选项后，才能看到下一个两条路径上的各个选项，每回合你需要通过选择路径，从而出发不同路径上的对应选项，使最终数值满足特定条件，该条件为大于每个节点要求的数值。

这是完整的抽象出来的，小游戏上的问题

这种问题其实是一种非常经典的图规划问题，游戏 杀戮尖塔 的核心设计本质上就是一种图规划问题

贪心的失效？

第一感觉是去想贪心

我们按照计算的影响级别来进行贪心，增肯定大于减，所以乘法和加法的选择优先级肯定会大于除法和减法，然后增加的情况中，乘法选择优先级大于加法，然后在相同的抉择中，两者的增倍数字谁大谁优，反之，面对必须减少的情况，减法的优先级肯定要大于除法，然后在相同的抉择中，两者谁减或者除的数字谁小谁优先

优先级排序 → 乘（大倍率） > 加（大数值） > 减（小数值） > 除（小倍率）

但是实际上，贪心是不行的，贪心可能陷入局部最优的困难

我们用具体例子看 “局部最优如何坑了全局最优”：

在你到达某一步的时候，你有 3 个人，如果这时候遇到了乘以2 和 增加4，按照上述情况，乘法的情况更优先，但是就算是玩弱智广告小游戏的人都知道，此时的增加4，是优于 乘以 2 的

想一个减少的情况，也是如此

这种情况贪心策略下，当前选择造成的结果，是不能按照简单的，通过选择影响更大的情况考虑的，因为不同基数下，加（减）法和乘（除）法的影响是无法一概而论的。

也就是，乘法的 “倍率优势” 需要 “基数足够大” 才成立，当基数很小时，加法的 “固定增量” 反而更优。

所以我们考虑另外一种贪心策略，比较结果数值，每一回合，我都选择让当前数值变得最大的那个操作

在第 t 回合，我们有两个选择（函数）：fL(x) （左侧路径）和 fR(x)（右侧路径）。该贪心策略定义如下 xt = max(fL(xt − 1), fR(xt − 1)) 但是这种情况也会出问题，为什么呢？

数学上，局部最优解只有当整个系统满足无后效性（Markov Property）*且*单调递增时，局部最优才等于全局最优。但是小游戏的设定中，有个核心因素会打破这个条件

会出现负数，如果减少到负数了，一切就都改变了，单调递增被打破了

例如，你当前的人数是10

  • 左侧路径：−10 × − 2
  • 右侧路径：+10 × − 2

按照这种贪心的情况，选择右侧路径的 +10 是满足结果更大的，但是下一步众生平等的× − 2，会让你的结果直接劣化，反而一开始 −10 是更优秀的情况

只有当游戏中，数值计算只有加减乘除，且数值始终保持为正数。那么每一步选择让当前数值最大的选项，必定能让最终结果最大。这种贪心策略才成立。

看起来完美无暇的策略，我的思考指向问题的根本，每步都尝试最大，那么为什么还是发生了这种看起来很好笑的巨大破绽？

因为贪心算法没有前瞻性，贪心算法有效的基本前提是系统的算子必须是单调递增（Monotonically Increasing）的。 一旦未来存在负倍率，当前回合的“最大值”必然对应未来的“最小值”。

所以这个问题，贪心真的失效了吗？

我看未必，所以我打了个？，在上面的标题上

因为实际的小游戏，你是有视野的，至少能看到两步没有选择的情况，那么就可以根据这个修正策略

如果出现了经过某步计算是负数的情况，那么当前回合的最优策略应该是最小化数值（尽可能接近 0 的正数，或者更小的负数），而不是最大化数值。

但是如果我们考虑去除负数，也就是不会出现乘以负数的情况，而且保持数值始终为正数的情况，那贪心就真的复活了

因为单调递增的这一个状态被恢复了

那么每一步选择让当前数值最大的选项，必定能让最终结果最大。

只要基数越大，经过同样的运算后，结果一定越大。 在这种设计下，玩家只需要算每一步的小学数学题，选大的那个就行，不存在“策略性”，只有“计算力”。

考虑每一步不能更换路径

问题改变

那么问题可以被修整成这样一个很成熟的情况

[CF2078D Scammy Game Ad][https://www.luogu.com.cn/problem/CF2078D]

CF2078D Scammy Game Ad

题目描述

考虑以下游戏。

游戏中每个关卡包含 n 对门。每对门包含一个左门和一个右门。每个门执行以下两种操作之一：

  • 加法操作 (+ a)：将该通道的人数增加固定值 a。
  • 乘法操作 (× a)：将该通道当前人数乘以整数 a。这意味着该通道人数将增加 (a − 1) 倍当前值。

每个操作产生的新增人员可以分配到任意通道。但已存在于某个通道的人员不可转移到另一个通道。

初始时，每个通道各有 1 人。你的任务是确定关卡结束时可达到的最大总人数。

输入格式

第一行输入整数 t（1 ≤ t ≤ 104）——测试用例数量。

每个测试用例的第一行包含一个整数 n（1 ≤ n ≤ 30）——门对的数量。

接下来每个测试用例的 n 行依次描述每对门的左门和右门信息。每个门的信息以 + a（1 ≤ a ≤ 1000）或 × a（2 ≤ a ≤ 3）形式给出，其中 a 为整数。

输出格式

对于每个测试用例，输出一个整数——关卡结束时的最大总人数。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
4
3
+ 4 x 2
x 3 x 3
+ 7 + 4
4
+ 9 x 2
x 2 x 3
+ 9 + 10
x 2 + 1
4
x 2 + 1
+ 9 + 10
x 2 x 3
+ 9 x 2
5
x 3 x 3
x 2 x 2
+ 21 + 2
x 2 x 3
+ 41 x 3

输出 #1

1
2
3
4
32
98
144
351

说明/提示

第一个测试用例的最优操作方式如下：

初始时，左通道人数 l = 1，右通道人数 r = 1。

通过第一对门后：

  • 左门产生 4 人（加法操作），右门产生 1 ⋅ (2 − 1) = 1 人（乘法操作）
  • 总新增 4 + 1 = 5 人，分配 2 人到左通道，3 人到右通道
  • 结果：l = 1 + 2 = 3，r = 1 + 3 = 4

通过第二对门后：

  • 左门产生 3 ⋅ (3 − 1) = 6 人（乘法操作），右门产生 4 ⋅ (3 − 1) = 8 人（乘法操作）
  • 总新增 6 + 8 = 14 人，均分 7 人到两个通道
  • 结果：l = 3 + 7 = 10，r = 4 + 7 = 11

通过最后一对门后：

  • 左门产生 7 人（加法操作），右门产生 4 人（加法操作）
  • 总新增 7 + 4 = 11 人，分配 6 人到左通道，5 人到右通道
  • 结果：l = 10 + 6 = 16，r = 11 + 5 = 16

最终总人数为 16 + 16 = 32。

贪心打赢复活赛了

这种情况跟我们之前的分析就完全不同了，这个问题完全可以使用贪心来解决

首先，这个问题涉及到存量和增量不同分配的情况

  • 已经在某个通道（左或右）的人。这部分是不可流动资产（Fixed Assets）。一旦选定，无法更改。
  • 每一关操作产生的新人。这部分是高流动性现金（Liquid Cash）。题目明确说明，每个操作产生的新增人员可以分配到任意通道。

那么，这个“增量可任意分配”。这意味着，我们在第 i 关产生的所有收益，在第 i+1 关开始前，都可以毫无损耗地投资到我们认为回报率最高的那个通道中。

我们假设第 i 关结束后，我们拥有总人数 Si，我们需要决定如何将新增的人数 Δi 分配给路径 L 和R，以便在游戏结束时获得最大的 Sfinal。

我们担心的情况就是，如果我现在为了贪图第$ i+1关的蝇头小利，把人全放左边，会不会导致我在第i+2$关错过右边的一个超级加倍？

秉持着少赚就是亏了的原则，我们分析一下

假设上下两条路，分别是+5，×10 和 +1，×100

首先，我们在上面这条路这时候有x人，这x人我全部给到 +5，因为他比+1多，然后这时候我就有了x + 5人

拿着这产生的5个人，我放到下面这条路，下面这条路我有p人，这时候，我就有了p + 500人

当我们尝试分析的时候，会发现，如果你的从头就开始规划一切，把所有产生出来的流动的人数，都投资到结果更大的路径，那么你一定是能赚到最大价值的，因为你固定的内容越少，可以支配的就越多，可以支配的内容一定会产生更大的价值，那么这样我们就可以推导出这样的一个策略 (Base × A) × B  >  Base × B 所以最大化当前的增量，等同于最大化未来的投资本金。局部最优（当前关卡产出最大化）直接导向全局最优。

举个例子，我们在一开始，上下两条路各有一个人，上下两条路分别还是+5，×10 和 +1，×100

  • 第一个门：

    • 在上路：1 经过了 +5 门，变成了 6，活动人数 5
    • 在下路：1 经过了 +1 门，变成了 2，活动人数 1

    我们把这活动的六个人，全部移动到下路，也就是移动上路五个人到下路

  • 第二个门：

    • 在上路：1经过了 ×10 门，变成了 10，活动人数 9
    • 在下路：6+1 经过了 ×100 门，变成了 700，活动人数 699

也就是说，不会出现五个人在上面最优，三个人在下面最优的抽象情况，所以完全分开摆放到最优的一侧是有必要的，通过一道门后，只有两种决策，产生的新人全部放到上面或者下面

所以可以考虑这样的代码来解决这个问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (sc.hasNextInt()) {
            int t = sc.nextInt();
            while (t-- > 0) {
                solve(sc);
            }
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        
        // 存储每一关的操作信息
        // types: 0 代表 '+', 1 代表 'x'
        // vals: 对应的数值
        int[][] leftTypes = new int[n][1];
        int[][] leftVals = new int[n][1];
        int[][] rightTypes = new int[n][1];
        int[][] rightVals = new int[n][1];

        for (int i = 0; i < n; i++) {
            // 读取左门
            String s1 = sc.next();
            leftTypes[i][0] = s1.equals("+") ? 0 : 1;
            leftVals[i][0] = sc.nextInt();
            
            // 读取右门
            String s2 = sc.next();
            rightTypes[i][0] = s2.equals("+") ? 0 : 1;
            rightVals[i][0] = sc.nextInt();
        }

        // 初始状态：左右各 1 人
        long l = 1;
        long r = 1;

        for (int i = 0; i < n; i++) {
            // 1. 计算当前这一关产生的增量
            long gainL, gainR;

            // 左边增量
            if (leftTypes[i][0] == 0) { // 加法
                gainL = leftVals[i][0];
            } else { // 乘法: 增量 = 当前人数 * (倍率 - 1)
                gainL = l * (leftVals[i][0] - 1);
            }

            // 右边增量
            if (rightTypes[i][0] == 0) { // 加法
                gainR = rightVals[i][0];
            } else { // 乘法
                gainR = r * (rightVals[i][0] - 1);
            }

            long liquid = gainL + gainR; // 本轮产生的可自由分配的总流动人数

            // 2. 贪心决策：展望未来，决定将 liquid 投给谁
            // 默认投给左边 (target = 0)，如果右边更好则改为 1
            int target = 0; 

            for (int k = i + 1; k < n; k++) {
                int rankL = getRank(leftTypes[k][0], leftVals[k][0]);
                int rankR = getRank(rightTypes[k][0], rightVals[k][0]);

                if (rankL > rankR) {
                    target = 0; // 左边优，投左边
                    break;
                } else if (rankR > rankL) {
                    target = 1; // 右边优，投右边
                    break;
                }
                // 如果 rank 相等，继续看下一关 (k++)
            }

            // 3. 分配增量
            if (target == 0) {
                l += liquid;
            } else {
                r += liquid;
            }
        }

        // 输出最终总人数
        System.out.println(l + r);
    }

    // 定义操作的优先级（Rank）
    // x3 (Rank 2) > x2 (Rank 1) > + (Rank 0)
    // 理由：乘法能利用累积的人数产生指数级增长，而加法收益是固定的。
    private static int getRank(int type, int val) {
        if (type == 0) { // 加法
            return 0;
        } else { // 乘法
            if (val == 3) return 2;
            else return 1; // val == 2
        }
    }
}
image-20251127205331096

可以发现，贪心在这时候就能打赢复活赛

为什么？

我觉得你能分析出来它满足的是单调递增的条件））））

状态转移有后效性吗

可以把上面的贪心思考成状态转移，这才是这道题的重量级的部分

我们上述思考的条件还是可以拿过来，就是，全部摆在一侧是产生最优解的必要条件，没有必要分开摆放，而且加法门加的数量是固定的，所以加法门，也是一种乘法门，可以进行转换

首先，状态定义可以这样思考

在第 i 关开始前，我们拥有的唯一“资源”是上路的人数 Li 和下路的人数 Ri。由于总人数 Si = Li + Ri，我们只需要知道总人数和其中一个通道的人数，就能确定完整状态。

  • 状态： dp[i][Li] 表示在第 i 关开始时，上路人数为 Li 时，能达到的最大总人数 Si。

那么，状态转移就按照题目思考

在第 i 关，两扇门会产生增量 ΔSi：

  • 上路门产生： ΔLi = if (+a) then a else Li(a − 1)
  • 下路门产生： ΔRi = if (+a) then a else Ri(a − 1)
  • 总增量： ΔSi = ΔLi + ΔRi

此时，我们需要决定将这 ΔSi 个人分配多少到上边（记为 k），多少到下边（ΔSi − k）。

  • 转移方程： Li + 1 = Li + k, Ri + 1 = Ri + (ΔSi − k)

继续思考，每个小人是独立的，也就是，我在这个门后进入赛道和在别的门后面进入赛道，是不会互相影响的，所以说，我们可以只考虑一个人的情况，也就是考虑 1 个人从某道门后开始，最终可以变成多少人

因为假设在第 i 步，通道中有一个人。如果这一步是乘法操作 ×a，那么这个人会变成 a 个人。按照题目规则，这 1 个人必须留在原通道，而新增的 a − 1 个人可以自由分配。为了最大化最终结果，这 a − 1 个新增的人显然应该被放到从第 i + 1 关开始，贡献价值更高的那条赛道。

定义“单位贡献度” f(i, lane)

  • f(i, 0)：第 i 对门操作结束后，位于左通道的 1 个人，到游戏结束时一共能变成多少人。
  • f(i, 1)：第 i 对门操作结束后，位于右通道的 1 个人，到游戏结束时一共能变成多少人。

考虑第 i 关的左门（lane 0），如果它是 ×a：

  1. 原有的 1 个人留在左通道，到结尾变成 f(i, 0) 人。
  2. 产生的 a − 1 个新人，我们会把他们全部放入 f(i, 0) 和 f(i, 1) 中较大的那个，到结尾变成 (a − 1) ⋅ max (f(i, 0), f(i, 1)) 人。

所以，第 i 关开始前（即第 i − 1 关结束后）左通道的这 1 个人，其总价值为：f(i − 1, 0) = f(i, 0) + (a − 1) ⋅ max (f(i, 0), f(i, 1))

而且加法门 +a 与乘法门的不同之处在于：它的增量是固定的，不依赖于当前通道有多少人。

在第 i 关，如果左门是 +aL，右门是 +aR：

  • 这 aL + aR 个新人是凭空产生的。
  • 我们同样会将他们分配到未来价值更高的通道。
  • 这部分的贡献就是：(aL + aR) ⋅ max (f(i, 0), f(i, 1))。

所以如果是加法门 +a，由于加法产生的人数不取决于当前人数，所以原有的人通过加法门时，其价值不发生变化：f(i − 1, 0) = f(i, 0)。

状态定义和状态转移方程就会出现再次的变化 f(i, {0, 1}) = 1 个小人从(上/下)i 道门后开始，最终可以变成的人数

f(i − 1, 0) = f(i, 0) + muli, 0 × max {f(i, 1), f(i, 0)}

f(i − 1, 1) = f(i, 1) + muli, 1 × max {f(i, 1), f(i, 0)}

探讨一点？常常说，动态转移没有后效性，如果有后效性，那么就是状态定义出现了问题，即“未来与过去无关，只与当前状态有关”。那么从这里面，是怎么看出来的

如果你认为“我现在把人放左边，可能会导致以后右边翻倍时人不够”，这听起来像是过去的操作影响了未来的潜力。

在这一题中，无论你之前是如何凑齐这 Li 和 Ri 人的，只要此时此刻你的 (Li, Ri) 确定了，第 i 关产生的收益 ΔSi 就是确定的。

更重要的是，收益函数是线性的。

设第 j 关后的总人数为 Sj + 1，它其实是 Li 和 Ri 的线性组合。

如果我们把第 i 关产生的“新增益” ΔSi 全部投向未来产出比（即后续所有倍数之积）更高的那一侧，那么最终的总人数一定是最大的。

由于收益函数是线性的，最大值一定在边界取得。这意味着：我们不需要尝试分配 k 个人，只需要要么全给左边，要么全给右边。

对应实现的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package 动态规划.subject.线性dp.CF2078DScammyGameAd;

import java.util.*;
import java.io.*;

public class Main {

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    static class Door {
        char type;
        long val;

        Door(String s, long v) {
            this.type = s.charAt(0);
            this.val = v;
        }
    }

    public static void main(String[] args) {
        FastReader fr = new FastReader();
        PrintWriter out = new PrintWriter(System.out);

        int t = fr.nextInt();
        while (t-- > 0) {
            int n = fr.nextInt();
            Door[][] doors = new Door[n + 1][2];

            for (int i = 1; i <= n; i++) {
                // 左门
                doors[i][0] = new Door(fr.next(), fr.nextLong());
                // 右门
                doors[i][1] = new Door(fr.next(), fr.nextLong());
            }

            // f[i][0] 表示第 i 关结束后，在左通道的 1 个人到终点能变成多少人
            // f[i][1] 表示第 i 关结束后，在右通道的 1 个人到终点能变成多少人
            long[][] f = new long[n + 1][2];

            // 基础状态
            f[n][0] = 1;
            f[n][1] = 1;

            for (int i = n; i >= 1; i--) {
                long maxFuture = Math.max(f[i][0], f[i][1]);

                // 处理左门对上一关左通道人数的贡献
                if (doors[i][0].type == 'x') {
                    // 乘法门：原有的 1 人留下，新增的 (val-1) 人去未来价值更高的通道
                    f[i - 1][0] = f[i][0] + (doors[i][0].val - 1) * maxFuture;
                } else {
                    // 加法门：原有的 1 人直接通过，不产生基于人数的增量
                    f[i - 1][0] = f[i][0];
                }

                // 处理右门对上一关右通道人数的贡献
                if (doors[i][1].type == 'x') {
                    f[i - 1][1] = f[i][1] + (doors[i][1].val - 1) * maxFuture;
                } else {
                    f[i - 1][1] = f[i][1];
                }
            }

            // 计算最终总人数
            // 1. 初始在左右通道的各 1 人的最终贡献
            long totalMax = f[0][0] + f[0][1];

            // 2. 累加所有加法门产生的固定人数贡献
            for (int i = 1; i <= n; i++) {
                long maxFuture = Math.max(f[i][0], f[i][1]);
                if (doors[i][0].type == '+') {
                    totalMax += doors[i][0].val * maxFuture;
                }
                if (doors[i][1].type == '+') {
                    totalMax += doors[i][1].val * maxFuture;
                }
            }

            out.println(totalMax);
        }
        out.flush();
        out.close();
    }
}
image-20251227193229233

可以发现，动态规划快了很多

逆向状态转移例题

洛谷 P1412

这道题（P1412 经营与开发）与你之前看到的 CF2078D 有着异曲同工之妙。它们的核心逻辑都基于一个深刻的 DP 思想：贡献度的线性比例性。

在动态规划中，正向 DP 关注的是“我从哪里来”，它必须记录下所有能影响未来的历史状态（在这里就是能力值 p）。

而 逆向 DP 关注的是“我到哪里去”。当我们从后往前推时，我们实际上是在计算 “单位能力的含金量”。

  • 在第 n 步，1 单位能力的价值就是它能采到的最后一点矿。
  • 在第 n − 1 步，1 单位能力的价值取决于它是现在采了变卖，还是留着在第 n 步变卖。

如果我们尝试正向推导，状态可能是 dp[i][p]，表示到达第 i 个星球时，钻头能力为 p 时的最大收益。

  • 由于损耗和修复是按百分比（1 − k% 或 1 + c%）计算的，能力值 p 会变成一个非常细碎的浮点数。
  • 状态空间几乎是无限的，无法通过数组记录。

观察收益公式：

  • 资源型收益：ai × p
  • 维修型支出：bi × p

你会发现，无论你在哪一关，当前的收益和未来的潜力都与当前的能力值 p 成正比。

如果当前能力值 p 翻倍，那么从这一刻起直到游戏结束，你所能获得的所有金钱都会翻倍。

这启发我们将 “当前拥有 1 单位能力值，从现在开始到结束能获得的最大收益” 定义为状态。

设 f[i] 表示：在开始处理第 i 个星球时，若此时钻头能力为 1，从 i 到 n 号星球能获得的最大利润。

场景 A：星球 i 是资源型（ai）

  1. 开采：立即获得 ai × 1 的收益。此后能力值变为 1 × (1 − 0.01k)。这剩余的能力在未来能带来的收益是 (1 − 0.01k) × f[i + 1]。
    • 总收益：ai + f[i + 1] × (1 − 0.01k)
  2. 不开采：能力值保持 1 进入下一关。
    • 总收益：f[i + 1]

所以：f[i] = max (ai + f[i + 1] × (1 − 0.01k), f[i + 1])

场景 B：星球 i 是维修型（bi）

  1. 维修：立即支付 bi × 1 的费用。此后能力值变为 1 × (1 + 0.01c)。
    • 总收益：−bi + f[i + 1] × (1 + 0.01c)
  2. 不维修：能力值保持 1 进入下一关。
    • 总收益：f[i + 1]

所以：f[i] = max (−bi + f[i + 1] × (1 + 0.01c), f[i + 1])

当我们推算到 f[1] 时，它表示“初始能力为 1 时”的最大收益。

题目给定的初始能力是 w，所以最终答案就是：f[1] × w。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        if (!sc.hasNextInt()) return;
        int n = sc.nextInt();
        double k = sc.nextDouble();
        double c = sc.nextDouble();
        double w = sc.nextDouble();

        // 存储星球信息，因为需要逆推
        int[] type = new int[n + 1];
        int[] val = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            type[i] = sc.nextInt();
            val[i] = sc.nextInt();
        }

        // f[i] 表示从第 i 个星球开始，初始能力为 1 时的最大收益
        // 实际上只需要一个变量滚动更新即可
        double f_next = 0;

        double k_mul = 1 - 0.01 * k;
        double c_mul = 1 + 0.01 * c;

        for (int i = n; i >= 1; i--) {
            if(type[i] == 1){
                // 资源型：max（开采，不开采）
                f_next = Math.max(f_next, val[i] + f_next * k_mul);
            }else{
                // 维修型：max(维修, 不维修)
                f_next = Math.max(f_next, -val[i] + f_next * c_mul);
            }
        }

        // 最终结果乘以初始能力 w
        System.out.printf("%.2f\n", f_next * w);
    }
}

image-20251227194527727

考虑每一步的生存压力

问题重构

一开始，我们拥有一个小人1个（其实这个初始数值可以是任何数，但是在不是1的情况下真的会不太一样），场地上一共两个路径，而且每条路径中存在多个路径选项，每个选项对应不同的数值增益 / 倍率。一回合设为你前进一次，经过某条路径上的一个条件，每回合只有在经过一条路径上的一个选项后，才能看到下一个两条路径上的各个选项，每回合你需要通过选择路径，从而出发不同路径上的对应选项，使最终数值满足特定条件，该条件为大于每个节点要求的数值。

我们把 使最终数值满足特定条件，这部分的要求，改作为每步的一个要求放进去，而且略微修改

每进行完一次选项的选择，我们都要面对一次”敌军的冲击”，我们的人数会减小给定该选项中限制条件的数值

人数为0，你无法继续前进

你还能到达彼岸吗

现在，我们的每一步操作不仅仅是 f(x)（增益），变成了 f(x) − C（增益后扣除生存成本）。

  • 状态：xt （当前小人数值）。
  • 动作：选择路径 L或 R
  • 结算公式：xt + 1 = Op(xt) − Costnode
  • 生存约束：xt + 1 > 0（如果不满足，该路径权重归零或视为负无穷）

注意，此时，环境限定没有负数乘法，且数值始终为正依旧生效。

但是，你不能在选择之前，看到那笔“过路费”，做决定时，只知道当前的收益，不知道下一站的代价。