P11233 [CSP-S 2024] 染色
Tag：DP、前缀和
题目描述
给定一个长度为 \(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\leq T\leq 10\)，\(2\leq n\leq 2\times 10^5\)，\(1\leq A_i\leq 10^6\)。
分析
考虑 \(\text{DP}\)。
在正式开始思考如何设计状态和转移方程之前， 我们可以先捏几个特殊情况， 来观察一下是否存在一些好的性质， 不管做什么题，绝大多数时候这种行为都是对我们解题有帮助的。
比如对于这个题而言，我们先看一个 \(\{1,2,2,3,3,1\}\) 的样例， 这个样例我们可以看出答案是 \(6\)，开始和结束的 \(1\) 中间包含了 \(3\) 和 \(2\) 两组相邻相等数字。 我们只需要把 \(3\) 和 \(2\) 染成一种颜色，把 \(1\) 染成另一种颜色就可以了。 这个样例可以启示到我们，如果一对相同数字之间存在一组或多组相邻的相同数字， 我们可以选择把这些数字都染成同一种颜色，让它们对答案做出贡献， 之后我们把两边的被分开的相同数字染成相同颜色，即可得到局部最优解。
再试图搓一个样例研究一下，比如 \(\{1,2,3,3,2,1\}\)， 对于这组样例，模拟一下可以发现答案为 \(5\)， 在这个样例之中，包含了上述所提到的一个结论， 对于两个相同数字之间所有相邻的相同数字， 我们都可以直接把它们染相同颜色添加到答案中。 并且这种情况可以忽略掉中间的其他数字， 举个例子 \(\{9,1,1,3,3,4,5,7,7,9\}\)， 在这个例子中，我们可以把第一个和最后一个 \(9\) 染上相同的颜色， 中间的所有其他数字都染另一种颜色，这样我们就可以得到最大的答案。
现在我们尝试定义 \(\text{DP}\) 的实际意义， 我们直接定义 \(dp[i]\) 为最简单且浅显的从头到第 \(i\) 位的答案。 来尝试一下在这种定义之下是否可以转移。 我们可以对于每一个 \(i\)，遍历 \(1\) 到 \(i-1\)， 找到距离 \(i\) 最近的与其数字相同的位置， 之后遍历这其中有多少相邻数字，把它们加到答案里。
上述式子中 \(j\) 代表距离 \(i\) 最近的相同数字所在位置。
这个转移不难实现，但是其时间复杂度为 \(O(n^2)\)， 无法通过全部测试用例，我们考虑如何优化这个转移。
在上述的转移中，有两个潜在的优化，一个是如何快速找到一个数字上一次出现的位置， 另一个是是否存在一个办法快速找到 \([j,i]\) 区间内有多少相同相邻的数字，它们的和是多少。
第一个优化是 trivial 的， 我们直接开一个 \(lst\) 数组，其具体意义为 \(lst[i]\) 是数字 \(i\) 上一次出现的位置。
对于如何快速确定一个区间内相邻相等数字的和， 我们可以使用前缀和：
于是我们可以优化之前的转移：
如果 \(A[i]\) 未曾出现过，直接让 \(dp[i]\) 继承 \(dp[i-1]\) 的答案即可。 于是我们成功把 \(O(n^2)\) 的转移优化到了 \(O(n)\)，真不错。
代码实现
int lst[1000005];
void NeverSayNever() {
for (int i = 0; i < 1000005; ++i) {
lst[i] = 0;
}
int n; cin >> n;
vector<int> vec(n+1),pre(n+1),dp(n+1);
for (int i = 1; i <= n ; ++i)
cin >> vec[i];
for (int i = 2; i <= n ; ++i) {
if (vec[i] == vec[i - 1])
pre[i] = pre[i - 1] + vec[i];
else
pre[i] = pre[i - 1];
}
for (int i = 1; i <= n ; ++i) {
dp[i] = dp[i - 1];
if(lst[vec[i]])
dp[i] = max(dp[i],dp[lst[vec[i]] + 1] + vec[i] + pre[i] - pre[lst[vec[i]] + 1]);
lst[vec[i]] = i;
}
cout << dp[n] << endl;
}
日志
本页面创建于 2024/03/14 22:53
特别鸣谢：
Boboge以及Nelofus/Ackerlanna的格式指导