本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-21 18:55:16

经过 @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)$$

$val(x,y)$ 表示令 $[x,y]$ 是一个同色区间，其贡献是多少。

这里我们可以用前缀和来优化。令 $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}$$

代码

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