D. 欺诈游戏广告

---

题意简述

初始时左右两条车道各有 $1$ 人。 每一对门会产生新增人数，这些新增的人可以任意分配到左/右车道，但一旦分配就不能再移动。 每个人会沿着自己所在车道走完后续所有门，你需要最大化最终总人数。

• 加法门 $+a$：固定新增 $a$ 人。
• 乘法门 $\times a$：新增人数为 当前车道人数 $\times (a-1)$。
• $n\le 30$，值域巨大但转移结构清晰。

---

核心观察

性质 1：加法收益与位置无关

所有加法操作产生的总增量是固定值，与分配方式无关，只与后续放大倍数有关。 因此可以把加法单独拎出来最后计算，只需要对乘法倍率做 DP。

性质 2：最优策略不会“分裂人群”

直觉上最优解一定满足： 所有新增的人，全部放在收益更高的那一条车道。 不需要一部分放左、一部分放右，集中放最优车道一定更优。

性质 3：每个人的贡献独立

每个人进入某条车道后，后续收益只由这条车道的门决定，与其他人无关。 因此总答案 = 初始两人的最终收益 + 所有新增人数 × 其所在车道的最终倍率。

---

DP 状态定义

倒推 DP（从最后一对门往前推）：

$$dp[i][0] = \text{一个人在第 $i$ 对门后处于左车道，走到最后的总收益倍数}$$ $$dp[i][1] = \text{一个人在第 $i$ 对门后处于右车道，走到最后的总收益倍数}$$

---

转移方程

对第 $i$ 对门：

• $mul[i][0]$：左门的乘法倍率（加法视为 $mul=1$）
• $mul[i][1]$：右门的乘法倍率
• $add[i]$：该对门产生的固定加法人数

转移 1（当前人在左车道）

$$dp[i-1][0] = dp[i][0] + mul[i][0] \cdot \max(dp[i][0], dp[i][1]) $$

含义：

• 原本这个人继续留在左车道：$dp[i][0]$
• 本轮乘法新增的人，全部放到后续收益更大的车道： $mul[i][0] \cdot \max(dp[i][0], dp[i][1])$

转移 2（当前人在右车道）

$$dp[i-1][1] = dp[i][1] + mul[i][1] \cdot \max(dp[i][0], dp[i][1]) $$

对称同理。

---

最终答案计算

初始左右各 $1$ 人，再加上所有加法产生的人：

$$ans = dp[0][0] + dp[0][1] + \sum_{i=1}^{n} add[i] \cdot \max(dp[i][0], dp[i][1]) $$

• $dp[0][0]$：初始左车道那个人的最终收益
• $dp[0][1]$：初始右车道那个人的最终收益
• 求和项：所有加法新增的人，都放到最优车道上的总收益

---

复杂度分析

• 状态数：$O(n)$
• 转移：$O(1)$ 每步
• 总复杂度：$O(n)$ 每组测试用例

完全可通过 $n\le 30$、$t\le 10^4$。

---

简要实现步骤

1. 从后往前倒序处理每一对门。
2. 对每个门提取 $mul[0],mul[1],add$。
3. 按转移方程更新 $dp[i][0],dp[i][1]$。
4. 最后按公式累加得到答案。