P11233

wosile · 2024-10-26 21:55:49 · 题解

我们可以设 f_{i,j} 表示考虑前 i 个数，与 A_i 颜色不同的最后一个数是 A_j 的最大价值，然后就得到了一个优秀的 50 分做法。f_{i,j} 可以转移到 f_{i+1,i} 和 f_{i+1,j}。

发现 f_{i+1,i} 好像很关键！于是我们直接把 f_i 的定义改成原来的 f_{i,i-1}。这样我们有 f_i=\max\limits_{j=1}^{i-1}(f_j+[A_{j-1}=A_i]A_i+\sum\limits_{k=j}^{i-2}[A_k=A_{k+1}]A_k)。这个 \sum 已经可以直接全局加做了，但是我们把相邻的相同数提前缩起来就没有这个 \sum 了。

然后只有一个前缀 max 和同颜色前缀 max。

一个我也不知道对不对但是过了大样例的代码：

#include<bits/stdc++.h>
using namespace std;
int a[200005],n,Tc;
typedef long long ll;
ll f[200005],mx[1000005],Mx;
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    scanf("%d",&Tc);
    while(Tc--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        ll ans=0;
        for(int i=1;i<n;i++)if(a[i]==a[i+1])ans+=a[i];
        n=unique(a+1,a+n+1)-a-1;
        Mx=0;
        memset(mx,-0x3f,sizeof(mx));
        for(int i=1;i<=n;i++){
            f[i]=max(Mx,mx[a[i]]+a[i]);
            Mx=max(Mx,f[i]);
            mx[a[i-1]]=max(mx[a[i-1]],f[i]);
        }
        printf("%lld\n",Mx+ans);
    }
    return 0;
}