题解：P5504 [JSOI2011] 柠檬

· · 题解

Sol

决策单调性写法。

题意很简单，就是要把序列分成若干块，使每块价值和最大。

考虑一个块的价值，我们容易发现一个性质：一个块可能当且仅当左右两端点同色且块内答案为左右两端点的颜色更新而来，否则这一块一定不优。

于是我们就可以写出转移方程了：

f_i=\max_{col_i=col_j} f_{j-1}+\mathrm{calc}(j,i)

这个方程有一定的简化，但应该不影响阅读。

我们会发现这个 DP 具有决策单调性，对于同一区间，因为同色，易得其决策点单调不增。也就是说，越往后的决策点，只会在前几个点被选择，此后就不优了。

因此我们可以单调栈实现。

值得注意的是，由于存在一个区间只有一个点的情况，我们应当先入栈，再更新 DP 值。

入栈时，对于栈顶二分其最后一个劣于新决策点的位置，倘若完全劣于新决策点即可出栈，否则将新决策点入栈即可。

int n;
int a[N];
int cnt[M];
ll sum[N];
ll f[N];
vec<pii> stk[M];int top[M];

inline ll calc(int i,ll t){return (i?f[i-1]:0)+a[i]*t*t;}
inline int find(int c,int x){
    int l=sum[x]-1,r=stk[c][top[c]].sec;
    while(l<r){
        int m=l+r+1>>1;
        if(calc(stk[c][top[c]].fir,m-sum[stk[c][top[c]].fir]+1)>calc(x,m-sum[x]+1))r=m-1;
        else l=m;
    }
    return l;
}
inline void Main(){
    read(n);
    rep(i,1,n)read(a[i]),sum[i]=++cnt[a[i]];
    rep(i,1,1e4)stk[i].resize(cnt[i]+2),stk[i][top[i]=1]={0,n};
    sum[0]=1;
    rep(i,1,n){
        int c=a[i],rt;
        while(stk[c][top[c]].sec<sum[i])--top[c];
        while(top[c]){
            rt=find(c,i);
            if(rt==stk[c][top[c]].sec)--top[c];
            else break;
        }
        if(rt>=sum[i])stk[c][++top[c]]={i,rt};
        f[i]=calc(stk[c][top[c]].fir,sum[i]-sum[stk[c][top[c]].fir]+1);
    }
    put(f[n]);
}