题解：P14294 [JOI2024 预选赛 R2] 白色灯 2 / White Light 2

给出一个只含有

\texttt{R}, \texttt{G}, \texttt{B}

的字符串

S(|S| = n)

，你可以执行任意次以下操作：

把第一个字符删去，代价为 $A$ 。
把最后一个字符删去，代价为 $B$ 。
修改任意一个字符，代价为 $C$ 。

你需要使操作后的字符串

S

满足以下任意一种要求：

$|S| = 0$ ；
$|S| \bmod 3 = 0$ 且 $\forall 0 \le i \le \dfrac{|S|}{3} - 1, S_{3i+1} = \texttt{R}, S_{3i+2} = \texttt{G}, S_{3i+3} = \texttt{B}$ 。

1 \le n \le 2 \times 10^5, 1 \le A, B, C \le 10^9

。

显然动态规划。先不考虑第二种操作。

令

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)

。

代码

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();
}

题解：P14294 [JOI2024 预选赛 R2] 白色灯 2 / White Light 2

文章操作

相关推荐

评论

题解：P14294 [JOI2024 预选赛 R2] 白色灯 2 / White Light 2