P11233 [CSP-S 2024] 染色【DP】 题解
__S08577__
·
·
题解
经过 @Dtw_ 和 @cybrex 的讲解之后，印象十分深刻，很多题解没有写清楚。
题意
题目
思路
由于 n \leq 2 \times 10^5，dp状态肯定只能设一维，不妨从最简单的状态开始考虑，我们设 f_i 为考虑前 i 个元素的得分最大值。
首先考虑朴素dp，考虑从 j 转移，便于理解，这里钦定从 j 转移是合法的（其实就是一个条件，a_i=a_j）。
说明：红色和绿色各是一种颜色，蓝色为不确定的涂色。
这里，有一个很显然的转移：
f_i=f_j+val(j+1,i-1)
这里我们可以用前缀和来优化。令 $sum_i$ 表示区间 $[1,i]$ 的贡献，则 $sum_i=sum_{i-1}+a_i \times [a_i=a_{i-1}]$。
这样方程就优化到了 $O(n^2)$ 的复杂度，可以通过50分。
但是，不幸的告诉你，转移方程出现了一点错误。
如果上图中的蓝色为绿色，那么 $j+1$ 这个点会对 $j-1$ 这个点产生贡献，贡献不能简单的用 $val$ 来计算，因为如果用 $val$ 计算，$j+1$ 的代价一定为0（因为一定 $a_{j+1}\ne a_j$）。所以，转移方程不妨这么写：
$$f_i=a_i+val(j+2,i-1)+f_{j+1}=a_i+sum_{i-1}-sum_{j+1}+f_{j+1}$$
这是正确的转移方程。
考虑将 $O(n^2)$ 优化为 $O(n)$。
这里需要发现一个小性质，$i$ 只会从 最近的 使得 $a_i=a_j$ 的 $j$ 转移过来。
### 证明
绿色的是只能填同色，而红色是随意填。
不难发现，上面的是从 $k$ 转移，下面的是从 $j$ 转移
（这里钦定从 $i$，$j$，$k$ 转移都是合法的转移）。
观察可得，区间 $[i,j]$ 的贡献一样，下面浅红色区间 $[1,k)$ 的贡献一定不劣于上面深红色区间 $[1,k)$ 的。而下面浅红色区间 $(k,j)$ 显然不劣于上面的绿色区间 $(k,j)$。
（可以这么考虑，同色的贡献只有相邻两个 $a_i$ 相同的情况，而随便填的贡献一定不比同色少）。
性质成立，所以不需要枚举 $j$，只需要记录上一个与 $a_i$ 相同的 $j$ 的位置，记为 $lst_{a_i}$。
最终的转移方程即为：
$$f_i=a_i+sum_{i-1}-sum_{lst_{a_i}+1}+f_{lst_{a_i}+1}$$
这里有个小细节 如果 $lst_{a_i}=i-1$，那么前缀和就祭了。处理也很好处理，下标与 $i-1$ 取最小值即可。
最后最后的转移方程为：
$$f_i=a_i+sum_{i-1}-sum_{\min(i-1,lst_{a_i}+1)}+f_{lst_{a_i}+1}$$
## 代码
```cpp
void solve(){
memset(f,0,sizeof f); memset(lst,0,sizeof lst);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=n;i++)
if(a[i]==a[i-1]) sum[i]=sum[i-1]+a[i];
else sum[i]=sum[i-1];
for(int i=1;i<=n;i++){
f[i]=f[i-1];
if(lst[a[i]]) f[i]=max(f[i],a[i]+f[lst[a[i]]+1]+(sum[i-1]-sum[min(i-1,lst[a[i]]+1)]));
lst[a[i]]=i;
}
cout<<f[n]<<endl;
}
```