题解：P14294 [JOI2024 预选赛 R2] 白色灯 2 / White Light 2
Terminal_P
·
·
题解
给出一个只含有 \texttt{R}, \texttt{G}, \texttt{B} 的字符串 S(|S| = n)，你可以执行任意次以下操作：
- 把第一个字符删去，代价为 A。
- 把最后一个字符删去，代价为 B。
- 修改任意一个字符，代价为 C。
你需要使操作后的字符串 S 满足以下任意一种要求：
***
显然动态规划。先不考虑第二种操作。
令 $F_i(C)$ 为只考虑前 $i$ 个字符，处理后末尾字符为 $C$ 的最小代价。
显然我们有
$$
\left\{
\begin{aligned}
&F_i(\texttt{NULL}) &&= F_{i - 1}(\texttt{NULL}) + A \\
&F_i(\texttt{R}) &&= \min\{F_{i-1}(\texttt{NULL}), F_{i-1}(\texttt{B})\} + W(S_i \to \texttt{R}) \\
&F_i(\texttt{G}) &&= F_{i-1}(\texttt{R}) + W(S_i \to \texttt{G}) \\
&F_i(\texttt{B}) &&= F_{i-1}(\texttt{G}) + W(S_i \to \texttt{B})
\end{aligned}
\right.
$$
其中 $W(A \to B)$ 是代价增量函数，$W(A \to B) = C \times [A = B]$。
加入第二种操作，答案就是 $\min\limits_{i=1}^n \left\{F_i(\texttt{B}) + (n - i)B\right\}$ 和 $\min\limits_{i=0}^n \left\{F_i(\texttt{NULL}) + (n - i)B\right\}$ 的较小值。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。
::::success[代码]
```cpp
void solve() {
i64 n, a, b, c, ans = inf64;
std::string s;
std::cin >> n >> s >> a >> b >> c, s = ' ' + s;
std::vector f(2, std::vector(5, inf64));
// 0 = NULL, 1 = R, 2 = G, 3 = B;
f[0][0] = 0;
ans = n * b;
for (i32 i = 1; i <= n; i++) {
std::fill(f[i & 1].begin(), f[i & 1].end(), inf64);
f[i & 1][0] = f[i & 1 ^ 1][0] + a;
f[i & 1][1] = std::min(f[i & 1 ^ 1][0] + c * (s[i] != 'R'), f[i & 1][1]);
f[i & 1][1] = std::min(f[i & 1 ^ 1][3] + c * (s[i] != 'R'), f[i & 1][1]);
f[i & 1][2] = std::min(f[i & 1 ^ 1][1] + c * (s[i] != 'G'), f[i & 1][2]);
f[i & 1][3] = std::min(f[i & 1 ^ 1][2] + c * (s[i] != 'B'), f[i & 1][3]);
ans = std::min({ans, f[i & 1][3] + (n - i) * b, f[i & 1][0] + (n - i) * b});
}
std::cout << ans << endl;
return void();
}
```
::::