预计阅读时间：6 分钟
DP 状态设计
DP 的胜负手在状态定义——状态立住了，转移不过是水到渠成。本合集收录状态定义与递推方向设计类的题目（复杂度优化技巧类见《优化DP》），随训练持续补完。
CF 2078D - Scammy Game Ad（反向递推：等效乘数）
https://codeforces.com/problemset/problem/2078/D
题意
有 n 对门，每对门分左、右两个通道。初始时左右通道各有 1 个人，且已在通道内的人不能中途切换通道。
通过第 i 对门的某个具体门（左或右）时：
- 加法门
+ a：额外产生 a 个新人，该通道原有人数不变。 - 乘法门
x a：设该通道操作前有 P 人，操作后变为 P·a 人——相当于原有 P 人保持为「基底」，额外新增 (a-1)·P 个人。
规则核心：每对门操作完成后，这一步新产生的所有人（加法直接给的、乘法多出来的部分）可以被最优地分配到左或右通道，再进入第 i+1 对门。目标是最大化通过全部 n 对门后左右通道的总人数。
分析
已在通道内的人路径锁死，只有新产生的人可以自由分配——那么每一批新人应该被派去哪条通道，取决于两条通道未来的增值能力。这提示我们分两个阶段：
第一阶段：反向 DP 计算「未来潜力」（等效乘数）。 从后向前计算 l[i] 和 r[i]：
l[i]：1 单位的人从第 i 对门的左门进入，之后所有新产生的人都最优分配，到游戏结束时这个人（连同他引发产生的所有人）能贡献的最大总人数；r[i]：同理，从第 i 对门的右门进入。
第二阶段：正向模拟，用「未来潜力」做决策。 从第 0 关开始维护左右通道人数 people_l、people_r（初始均为 1）。对第 i 对门：
- 先按乘法门更新两通道的基数（原有人数倍增）；
- 算出这对门总共新产生了多少人（加法门直接给的 + 乘法门的 (a-1)·基数）;
- 比较
l[i+1]与r[i+1]，把全部新人统一分给潜力更大的那条通道。
边界条件
l[n] = 1
r[n] = 1
虚拟出第 n+1 关：它没有门，倍率为 1——1 个人走出去还是 1 个人。
递推式
若第 i 关左门是乘法门 x a：
l[i] = l[i + 1] + (a - 1) * max(l[i + 1], r[i + 1])
l[i+1]：最初进左门的那 1 个人沿左通道走到底，自身能产生的最终等效人数；(a - 1)：这个乘法门凭空多出 a-1 个与他潜力相同的人；max(l[i+1], r[i+1])：新增的每个人都会被派往下一关潜力更大的通道继续增值。
若第 i 关左门是加法门 + a：
l[i] = l[i + 1]
加法门不改变通过者本身的增值特性，这 1 个人的潜力完全由下一关决定（加法门产生的 a 个新人属于「新增人口」，在第二阶段正向模拟时才参与分配）。r[i] 的两种情况完全对称。
代码
t = int(input())
for _ in range(t):
n = int(input())
left = []
right = []
for _ in range(n):
a = input().split()
left.append([a[0], int(a[1])])
right.append([a[2], int(a[3])])
l = [0] * (n + 1)
r = [0] * (n + 1)
l[n] = 1
r[n] = 1
for i in range(n - 1, -1, -1):
if left[i][0] == '+':
l[i] = l[i + 1]
else:
l[i] = l[i + 1] + (left[i][1] - 1) * max(l[i + 1], r[i + 1])
if right[i][0] == '+':
r[i] = r[i + 1]
else:
r[i] = r[i + 1] + (right[i][1] - 1) * max(l[i + 1], r[i + 1])
l_people = 1
r_people = 1
l_new = 0
r_new = 0
for i in range(n):
if left[i][0] == '+':
l_new = left[i][1]
else:
l_new = l_people * left[i][1] - l_people
if right[i][0] == '+':
r_new = right[i][1]
else:
r_new = r_people * right[i][1] - r_people
if l[i + 1] > r[i + 1]:
l_people += l_new + r_new
else:
r_people += l_new + r_new
print(l_people + r_people)
未完待续，本合集随训练进度持续补完。
本文由 aboom 原创，转载请注明出处。