写了个裸的 $O(n^2)$ 过了。

民间数据有点水了吧。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
int dp[N],qz[N],a[N],T,n;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++)a[i]=read();
        memset(qz,0,sizeof qz);
        for(int i=2;i<=n;i++){
            if(a[i]==a[i-1])qz[i]=qz[i-1]+a[i];
            else qz[i]=qz[i-1];
        }
        for(int i=1;i<=n;i++){
            dp[i]=dp[i-1];
            for(int j=i-1;j>=1;j--){
                if(a[i]==a[j]){
                    dp[i]=max(dp[i],dp[j+1]+a[i]+qz[i-1]-qz[j]);
                    break;
                }
            }
        }
        cout<<dp[n]<<'\n';
    }
    return 0;
}

任意构造一个 $1$ 到 $n$ 的排列就可以卡成 $O(n^2)$ 的。

不过因为这样构造很容易把其他假做法放掉所以没有这么出？