P11233 [CSP-S 2024] 染色 题解
Exp10re
·
·
题解
赛前写过类似的 Trick。
结果一看怎么题解区没有一个和我思路一样的，补一个题解。
解题思路
记 f_i 表示位置 i 的颜色与位置 i-1 的颜色不同时前 i 位的得分最大值。
显然有一个 O(n^2) 转移的做法：
f_{i}=\max\limits_{1\leq j\lt i} (f_j+\sum\limits_{k=j+1}^{i-1} [a_k=a_{k-1}]a_k+[a_i=a_{j-1}]a_i)
边界为 f_1=0，答案为 f_{n+1}。
其中从 f_j 转移到 f_i 的含义为第 j 个数到第 i-1 个数颜色相同，第 j-1 个数与第 i 个数颜色相同且与中间的一段不同时的得分转移。
考虑优化，记：
a_i &\ a_{i}=a_{i-1} \\
0 &\ otherwise \\
\end{cases}
则上式可以被表示为：
f_{i}=\max\limits_{1\leq j\lt i} (f_j+\sum\limits_{k=j+1}^{i-1} b_k+[a_i=a_{j-1}]a_i)
则对 b 作前缀和，记 pre_i=\sum\limits_{j=1}^{i} b_j，则上式转移可以被优化至 O(n)：
f_{i} =\max\limits_{1\leq j\lt i} (f_j+pre_{i-1}-pre_{j}+[a_i=a_{j-1}]a_i)
提出去一个 pre_{i-1} 可以得到：
f_{i} =\max\limits_{1\leq j\lt i} (f_j-pre_{j}+[a_i=a_{j-1}]a_i)+pre_{i-1}
发现如果不考虑 [a_i=a_{j-1}]a_i 一项的话就是前 i-1 项的 f_{j}-pre_{j} 最大值与 pre_{i-1} 的和，而考虑 [a_i=a_{j-1}]a_i 得到的值一定比这个更大，即 f_{j}-pre_{j} 的前缀最大值与 pre_{i-1} 的和是 f_i 的一个下限，故将转移分开两块分别计数求更大值。
具体的，记 s_i=f_i-pre_i，则：
f_i=\max({\max\limits_{1\leq j\lt i} s_j},{\max\limits_{1\leq j\lt i,a_{i}=a_{j-1}} s_j+a_i})+pre_{i-1}
考虑将该转移式优化。
而对于后一项 $\max\limits_{1\leq j\lt i,a_{i}=a_{j-1}} s_j+a_i$ 则考虑到 $a$ 的值域较小，可以对于每一个 $a_i=x$ 的 $i$ 记录 $s_{i+1}+x$ 的最大值，记为 $mxn_x$，如此后面一项也可以 $O(n)$ 进行转移。
整理一下转移步骤：
- $f_{i}=\max(maxn,mxn_{a_{i}})+pre_{i-1}$。
- 用 $f_i-pre_i$ 更新 $maxn$。
- 用 $f_i-pre_i+a_{i-1}$ 更新 $mxn_{a_{i-1}}$。
$maxn$ 初始值为 $0$，所有 $mxn_i$ 初始值为 $-\infty$。
这个转移的复杂度显然是 $O(1)$，所有转移的时间复杂度之和是线性的。由此我们得到了 $O(T(n+V))$ 的解。
## 代码
读懂上面的部分，代码是好理解的。
```cpp
#include<bits/stdc++.h>
using namespace std;
const long long MAXN=1010010,INF=1e18;
long long f[MAXN],mxn[MAXN],maxn,pre[MAXN],a[MAXN],n;
void work()
{
long long i;
scanf("%lld",&n);
for(i=0;i<=MAXN-1;i++)
{
mxn[i]=-INF;
a[i]=0;
}
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
pre[1]=0;
for(i=2;i<=n;i++)
{
if(a[i]==a[i-1])
{
pre[i]=a[i];
}
else
{
pre[i]=0;
}
pre[i]+=pre[i-1];
}
maxn=0;
for(i=2;i<=n+1;i++)
{
f[i]=max(maxn,mxn[a[i]])+pre[i-1];
maxn=max(maxn,f[i]-pre[i]);
mxn[a[i-1]]=max(mxn[a[i-1]],f[i]-pre[i]+a[i-1]);
}
printf("%lld\n",f[n+1]);
return;
}
int main()
{
// freopen("P11233.in","r",stdin);
// freopen("P11233.out","w",stdout);
long long T;
scanf("%lld",&T);
while(T--)
{
work();
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
```