题解 P5504 【[JSOI2011]柠檬】

2019-10-23 10:56:15


广告


斜率优化好题。

首先有一个显然的性质:每一段左右端的贝壳大小一定相同,而且这一段的 $s_0$ 一定是左右端贝壳的大小。因为如果不是这样的话,我们显然可以把端点单独成一段,然后答案会变大。

设 $dp_i$ 表示前 $i$ 个贝壳最多可以得到多少柠檬, $c_i$ 表示 $i$ 是第几个 $a_i$ 大小的柠檬,容易得到状态转移方程

$$dp_i=\max_{j=1}^i\left\{dp_{j-1}+a_i(c_i-c_j+1)^2\right\}$$

把 $\max$ 里的东西拆开,并把所有项分为三类:

  • 与 $j$ 无关的: $a_ic_i\!^2+2a_ic_i+a_i$
  • 只和 $j$ 有关的: $dp_{j-1}+a_ic_j\!^2-2a_ic_j$ (注意, $a_i=a_j$ )
  • 既和 $i$ 有关又和 $j$ 有关的: $-2a_ic_ic_j$

令 $pre_i=a_ic_i\!^2+2a_ic_i+a_i$ , $k_i=2c_i$ , $x_i=a_ic_i$ , $y_i=dp_{i-1}+a_ic_i\!^2-2a_ic_i$ ,那么状态转移方程改写为:

$$dp_i=pre_i+\max_{j=1}^{i}\left\{-k_ix_j+y_j\right\}$$

把每个转移点看做一个点 $(x_j,y_j)$ ,那么我们相当于要找一个点,使得斜率为 $k_i$ 的经过它的直线的纵截距最大。

显然所有可能的转移点在上凸壳上;因为 $x_i$ 单增、 $k_i$ 单增,所以用单调栈维护上凸壳,栈顶为最优决策。

注意每次要把自己先加到单调栈中去再取栈顶转移。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#define re register
#define sqr(x) ((x)*(x))
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,V=10000+10;

int n,a[N],o[V],c[N];
int dp[N];
vector<int> Q[V];

inline int X(int i) { return a[i]*c[i]; }
inline int Y(int i) { return dp[i-1]+a[i]*c[i]*c[i]-2*a[i]*c[i]; }
inline double slope(int i,int j) {
    return 1.0*(Y(i)-Y(j))/(X(i)-X(j));
}
inline int calc(int i,int j) {
    return dp[j-1]+a[i]*sqr(c[i]-c[j]+1);
}

#define A Q[t][Q[t].size()-2]
#define B Q[t][Q[t].size()-1]

signed main() {
    n=read();
    for (re int i=1;i<=n;++i)
        a[i]=read(),c[i]=c[o[a[i]]]+1,o[a[i]]=i;
    for (re int i=1;i<=n;++i) { int t=a[i];
        while (Q[t].size()>=2&&slope(A,i)>=slope(A,B)) Q[t].pop_back();
        Q[t].push_back(i);
        while (Q[t].size()>=2&&calc(i,B)<=calc(i,A)) Q[t].pop_back();
        dp[i]=calc(i,Q[t].back());
    }
    printf("%lld\n",dp[n]);
    return 0;
}