P11233 [CSP-S 2024] 染色

难度	算法s	日期	题目链接
提高+/省选−	DP	2025-10-16	https://luogu.com.cn/problem/P11233

题意简述

给定一个长度为 $n$ 的正整数数组 $A$，其中所有数从左至右排成一排。

你需要将 $A$ 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：

设 $C$ 为长度为 $n$ 的整数数组，对于 $A$ 中的每个数 $A_i$（$1 \leq i \leq n$）：

• 如果 $A_i$ 左侧没有与其同色的数，则令 $C_i = 0$。
• 否则，记其左侧与其最靠近的同色数为 $A_j$，若 $A_i = A_j$，则令 $C_i = A_i$，否则令 $C_i = 0$。

你的最终得分为 $C$ 中所有整数的和，即 $\sum \limits_{i=1}^n C_i$。你需要最大化最终得分，请求出最终得分的最大值。

范围：$1\le n\le2\times10^5,1\le A_i\le1\times10^6$。

DP 状态设计

我们从 i=1 遍历到 i=n。

• struct {
      int score, at;
  } dpRed[...], dpBlue[...]

• 此时 dpRed[x].score 表示前 i 个数中，最后一个染红的数字为 x 时的最大得分；而 dpRed[x].at 表示这最后一个数字在哪里。类似地，我们再设计一个状态 dpBlue[]。

• 那么最终的答案就是 max(dpRed[A[n]],score, dpBlue[A[n]].score)。

怎么转移状态呢？

• 如果把 A[i] 染红，得分怎么计算？
  • 其实就是要决定，现在要选择上一个染红的数字为几的红色数字串后面。
  • 如果前面存在和 A[i] 相同的数字，且我们选择接上去，则红色带来的得分为 dpRed[A[i]].score + A[i]。假设这样的总得分为 scoreA。
  • 如果不存在，或者我们选择不接，则挨个枚举选择的的 dpRed[x]，红色带来的得分为 dpRed[x]。假设这样的总得分为 scoreB。
  • 染红后，蓝色带来的得分不会改变，不需要额外计算。
• 如果把 A[i] 染蓝，与上述过程同理，得到 scoreC、scoreD。

这样的做法是 $O(n^2)$ 的，稍后我们再来优化。先考虑：这种做法对吗？会不会重复？

• 假设当前 .at 不同的 dpRed[x] 和 dpBlue[y] ，其染色没有冲突，也就是没有“既把 A[x] 染成红又染成蓝，计算两次得分”这种情况。
• 我们计算当前得分时，保证了选择的最后一个节点不相同，即 dpRed[x].at != dpBlue[y].at。所以我们计算的操作不会产生新的冲突。