CSP前的最后挣扎

---

$Sol$

朴素dp是 $O(n2)O(n2)$ 的

设 $dp[i]dp[i]$ 表示前$ii$个可能产生的最大价值,直接暴力转移

一个显然的结论是: 把一段的首尾大小强制相同不会使答案变差

于是我们对于每一种大小分别考虑:

$dp[i]$=$max$ ( $dp[j]$+$s[i]$∗($sum[i]$−$sum[j]$+1)2 )

$dp[i]$=$max$ ( $dp[j]$+$s[i]$∗($sum[i]$−$sum[j]$+1)2 )

$sum[i]$$sum[i]$ 表示与ii号贝壳大小相同的ii的前缀的贝壳总数

首先从前往后 dp 值一定是不降的,对于两个可能的决策点 $j1$,$j2$($j1$<$j2$) $j1$,$j2$($j1$<$j2$)

由于后面那一坨平方项也是单增的,并且增加得很快,那么当 $j1j1$的转移由于$j2j2$ 时,$j1j1$在之后的决策过程中也必定会优于 $j2j2$

一个想法就是开一个栈,每次如果栈顶不优于第2个元素的时候就弹栈

但是可能会出现第3个元素能在更早的时间比栈顶优的情况,综合考虑的话我们就是要维护一个当前位置元素比它上面的元素优时的$sum[i]sum[i]$的最小值 递增的一个单调栈,这样我们每次从栈顶作为决策点就一定是最优的

其实每个决策点就是一个单调递增的二次函数

二分出函数图像的”交点”来做最优决策

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<set>
#include<vector>
using namespace std;
#define Set(a,b) memset(a,b,sizeof(a))
#define POW(a) ((a)*(a))
int n;
const int N=1e5+10;
const int MAXN=10200;
typedef long long ll;
int s[N];
int *st[MAXN];int top[MAXN];
int num[MAXN];
int pool[N<<1];
ll dp[N];
int lst[MAXN],pre[N],sum[N];
inline ll calc(int p,int x,int S){return dp[p-1]+1ll*S*POW(1ll*(x-sum[p]+1));}
#define INF 1e9
inline int query(int p,int q,int S)
{
    register int l=1,r=n,pos=n+1;
    while(l<=r){
        register int mid=l+r>>1;
        if(calc(p,mid,S)>=calc(q,mid,S)) r=mid-1,pos=mid;
        else l=mid+1;
    }
    return pos;
}
int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;++i) scanf("%d",&s[i]),++num[s[i]];
    int h=0;
    for(register int i=0;i<MAXN;++i;
    {
        st[i]=&pool[h];h+=num[i]+2;
    }
    register ll ans=0;
    for(register int i=1;i<=n;++i)
    {
        pre[i]=lst[s[i]];lst[s[i]]=i;sum[i]=sum[pre[i]]+1;
        register int x=s[i];
        while(top[x]>1&&query(st[x][top[x]-1],st[x][top[x]],x)<=query(st[x][top[x]],i,x)) --top[x];
        st[x][++top[x]]=i;
        register int p,q;
        for(p=st[x][top[x]],q=st[x][top[x]-1];top[x]>1;--top[x],p=q,q=st[x][top[x]-1]) if(calc(p,sum[i],x)>calc(q,sum[i],x)) break;
        dp[i]=calc(p,sum[i],x);
        ans=max(ans,dp[i]);
    }
    printf("%lld\n",ans);
}

祝各位

$\color{blue}{AKIOI}$