BZOJ-4709: [Jsoi2011]柠檬

Description

Flute 很喜欢柠檬。它准备了一串用树枝串起来的贝壳，打算用一种魔法把贝壳变成柠檬。贝壳一共有 N (1 ≤ N ≤ 100,000) 只，按顺序串在树枝上。为了方便，我们从左到右给贝壳编号 1..N。每只贝壳的大小不一定相同，贝壳 i 的大小为 si(1 ≤ si ≤10,000)。变柠檬的魔法要求，Flute 每次从树枝一端取下一小段连续的贝壳，并选择一种贝壳的大小 s0。如果 这一小段贝壳中 大小为 s0 的贝壳有 t 只，那么魔法可以把这一小段贝壳变成 s0t^2 只柠檬。Flute 可以取任意多次贝壳，直到树枝上的贝壳被全部取完。各个小段中，Flute 选择的贝壳大小 s0 可以不同。而最终 Flute 得到的柠檬数，就是所有小段柠檬数的总和。Flute 想知道，它最多能用这一串贝壳变出多少柠檬。请你帮忙解决这个问题。

发现对于一段中首尾两个元素的大小一定是相同的，如果不是相同的，那么可以将不同部分单独成段，解更优。
设dp[i]表示1~i的贝壳分段能边出的最多的柠檬，假设到了第i个位置，当前元素大小为si，sum[i]表示1~i中大小和i相同的贝壳的个数。
转移：dp[i]=max(dp[k-1]+s[i]*(sum[i]-sum[k]-1)^2) s[i]=s[k]。
可以斜率优化，对于每一种大小都维护一个栈即可。

#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,num[101000],s[101000],p[11000];
ll dp[101000];
vector<int>z[10100];
ll K(int i){return -2ll*s[i]*(num[i]-1);}
ll B(int i){return dp[i-1]+(ll)s[i]*(num[i]-1)*(num[i]-1);}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",s+i); 
        num[i]=num[p[s[i]]]+1;
        p[s[i]]=i;
    }
    ll x,ans=0;
    for(int i=1;i<=n;++i)
    {
        x=s[i]; dp[i]=dp[i-1]+s[i];
        if(z[x].size())
        {
            while(z[x].size()>1 && K(z[x][z[x].size()-1])*num[i]+B(z[x][z[x].size()-1])
                <= K(z[x][z[x].size()-2])*num[i]+B(z[x][z[x].size()-2]) ) z[x].pop_back();
            dp[i]=max(dp[i],K(z[x][z[x].size()-1])*num[i]+B(z[x][z[x].size()-1])+x*num[i]*num[i]);
            while(z[x].size()>1 && (B(i)-B(z[x][z[x].size()-1]))*(K(z[x][z[x].size()-2])-K(z[x][z[x].size()-1]))
                >=(B(z[x][z[x].size()-1])-B(z[x][z[x].size()-2]))*(K(z[x][z[x].size()-1])-K(i)) ) z[x].pop_back();
        }
        z[x].push_back(i);
        ans=max(ans,dp[i]);
    }
    printf("%lld",ans);
    return 0;
}