题目大意

n 个灯泡，每次选择一个灯泡，它会等概率变成 r/g/b 三种颜色之一。求在最优策略下，让所有灯泡最终同色的最小期望操作次数。

思路讲解

状态压缩为什么不会偏小

这里的状态写成 dp[a][b][c]，其中 a ≥ b ≥ c，只保留三种颜色数量的有序三元组，不再记录哪个数量对应 r/g/b。乍一看，这像是把颜色标签抹掉了，会不会让策略空间变大，从而让期望被算小。

💡 Note: 不会。原因是这道题的颜色标签本身完全对称：r/g/b 只是一组三个名字，操作概率、目标条件、代价都不依赖具体颜色名。

换句话说，任意两个状态只要颜色数量的多重集相同，比如 (5,3,2) 对应红多一点，或者绿多一点，它们只是把颜色名字重命名了一下。最优策略也可以跟着颜色重命名，所以期望值必须相同。

所以排序不是在额外合并“不等价”的状态，而是在把一整类只差颜色命名的等价状态合并。终态也同样忽略颜色：(n,0,0) 表示全红、全绿、全蓝这三个终态的共同代表，它们的期望都为 0。初态和终态都按同一套颜色对称性取商，因此不会影响答案。

真正需要小心的是：排序后做转移时，每次后继状态也必须重新排序；这样才是在等价类之间转移。

auto norm = [&](array<int, 3> x) {
    sort(x.begin(), x.end(), greater<int>());
    return x;
};

// 从当前有序状态转移后，必须再次 norm
nxt = norm(nxt);

额外坑：排序压缩后，不能只把“颜色没有变化”当自环；只要转移后的计数重新排序后仍等于当前 (a,b,c)，它就是同一个压缩状态，也要计入自环概率。

cur = (1, 1, 0);
pos = 1;

// b -> a: (2, 0, 0)
// b -> b: (1, 1, 0) self
// b -> c: (1, 0, 1) -> sort -> (1, 1, 0) self

// 所以 self = 2，不能固定乘 3/2；应使用：
E = (known + 1) / (1 - self / 3.0);

反向推导的定位

期望 DP 的建模仍然是正向的：站在当前状态写 “1 + 后继期望的平均”。按 max(a,b,c) 从大到小求值，只是为了让部分后继状态已经算过；这是实现技巧，不是思考方法本身。

push / pull 与倒序枚举的判断

push 和 pull 不是写法喜好，而是依赖方向问题。判断标准是：处理到当前状态时，它的值是否已经完整确定；以及当前状态要读取的依赖是否已经算过。

写法	核心判断	适合场景	这题里的结论
push	处理到 cur 时，dp[cur] 已经完整确定，可以放心把贡献分发给 nxt。	DAG 拓扑序、前缀 DP、路径计数、概率分布传播。	排序压缩后有同层和自环，贡献可能推到已经处理过的位置，写起来容易漏。
pull	处理到 cur 时，cur 要读取的 dp[nxt] 都已经算好，然后由方程合成 dp[cur]。	min/max 转移、期望方程、自环移项、同层依赖比较绕的 DP。	本题期望式天然是 E(cur)=1+average(E(nxt))，自环和同层都能在当前方程里统一处理。

push：当前 dp[cur] 已经完整确定，把贡献分发给后继。适合 DAG 拓扑序、前缀 DP、路径计数、概率分布传播等场景。

// push: dp[u] 已经确定，向外分发贡献
for (auto v : nxt[u]) {
    dp[v] += dp[u] * w;
}

pull：当前 dp[cur] 要由若干已知状态合成。适合 min/max 转移、期望方程、自环移项、同层依赖方向复杂的场景。

// pull: 站在 u，读取已知状态来计算自己
dp[u] = init;
for (auto v : next(u)) {
    dp[u] = combine(dp[u], dp[v]);
}

这题更适合 pull，因为期望式天然是 E(cur) = 1 + average(E(nxt))。如果用 push，必须保证被推到的状态还没处理；但排序后的同层转移会让贡献方向变得麻烦，容易出现“加晚”。pull 则是先看完整当前方程，统计自环，再读取已经算好的后继。

倒序枚举的判断也不是看心理上从哪里出发，而是看依赖谁：算当前状态时，它依赖的状态必须已经算过。依赖更小下标就正序，依赖更大下标或更接近终点的状态就倒序。

枚举方向	判断标准	典型代码	本题对应
正序	dp[cur] 依赖更小的状态，比如 dp[i-1]、更短前缀、更少物品。	for (int i = 1; i <= n; ++i)	如果当前值依赖的是 a 更小 / b 更小的状态，才会正序。
倒序	dp[cur] 依赖更大的状态，或者更接近终点的状态，比如 dp[i+1]。	for (int i = n - 1; i >= 0; --i)	本题 dp[a][b][c] 依赖 a 更大，或同 a 下 b 更大的后继，所以 a、b 都倒序。

// 正序：dp[i] 依赖 dp[i - 1]
for (int i = 1; i <= n; ++i) {
    dp[i] = f(dp[i - 1]);
}

// 倒序：dp[i] 依赖 dp[i + 1]
for (int i = n - 1; i >= 0; --i) {
    dp[i] = f(dp[i + 1]);
}

对本题的 c > 0 状态，摸 c 后的非自环后继通常是 (a+1, b, c-1) 或同层的 sort(a, b+1, c-1)，也就是 a 更大，或同 a 下 b 更大。因此求值顺序选 a 倒序、b 倒序，让右边 dp[nxt] 先被算好。

for (int a = n - 1; a >= 0; --a) {
    for (int b = a; b >= 0; --b) {
        int c = n - a - b;
        // 计算 dp[a][b][c]
    }
}

一句话：这题是正向建模，反向求值；选择倒序不是因为从终态“反推过程”，而是因为当前状态的期望依赖更接近终态的后继状态。

AC 代码

待补。

心路历程

一开始容易把“倒序求值”误解成“从终态反推期望”。正确区分是：式子按当前状态正向建，代码按层倒序算。
另一个容易卡住的点是排序状态是否会压小答案；本质原因是颜色完全对称，所以这是合法的等价类压缩。

附件

待补 mentor.pdf / 源码附件。

Znzryb's Blog

Gym 106353 E - Erratic Lights