s考场心理剧

来到考场打开题目：

t1简单题，秒切

t2看到浮点数一眼跳过

t3看到想到dp但一眼没看出来，看t4

t4想到树但不会，回去看t3

突然感觉不对，怎么没有图论（孩子已经连续五场比赛没碰图论了，图论人哭哭）

t3思考中...想到一个假dp，大样例没过，再思考...

(1 hour later)想到贪心，维护最近左边出现的相同的数的位置，在维护一段区间里颜色都相同的贡献（接下来糖诗时刻）

维护区间想到线段树（糖死了），直接写了1h

写完后自信测样例，爆

又调了30min,没调出来，结果心态爆炸，不确定贪心对不对，也没想到前缀和，连 O(n^2) 暴力都没写，写了个 O(2^n) 的糖诗暴力，20tps(本来能写个50tps的(哭))

t3AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+5;
ll a[N],lst[N],t[N],qzh[N],dp[N],n;
int main(){
    ll q;cin>>q;
    while(q--){
        cin>>n;
        for(ll i=1;i<=N-1;i++)a[i]=t[i]=lst[i]=qzh[i]=dp[i]=0;
        for(ll i=1;i<=n;i++){
            cin>>a[i];
            lst[i]=t[a[i]];
            t[a[i]]=i;
            qzh[i]=qzh[i-1];
            if(a[i]==a[i-1])qzh[i]+=a[i];
        }
        ll ans=0;
        for(ll i=1;i<=n;i++){
            dp[i]=dp[i-1];
            if(lst[i])dp[i]=max(dp[i],dp[lst[i]+1]+a[i]+(qzh[i]-qzh[lst[i]+1]));
            ans=max(dp[i],ans);
//          cout<<dp[i]<<endl;
        }
        cout<<ans<<endl;
    }
}

——这坨东西和我考场上唯一的区别就是线段树和前缀和

最后30min写t2，然后式子居然写错了，连暴力都没写完，总之就是

寄