【LG5504】[JSOI2011]柠檬
题面
题解
考虑(dp)，令(f_i)表示(dp)到第(i)位且在第(i)位分段的最大值。
我们令题面中的(s_i)为(a_i)，那么对于一个转移点(j)，显然(a_i=a_j)，因为多余的颜色肯定无法产生贡献，不如不选。
令(c_i)为位置(i)的颜色第几次出现。
那么有转移方程：
[f_i=f_{j-1}+a_i(c_i-c_j+1)^2
]
推下式子：
[f_i=f_{j-1}+a_i(c_i^2+(c_j-1)^2-2c_i(c_j-1))\
Leftrightarrow f_{j-1}+a_j(c_j-1)^2=2a_ic_i(c_j-1)+f_i-a_ic_i^2
]
将这个式子看作一个一次函数(y=kx+b)，那么在这个式子中，(y=f_{j-1}+a_j(c_j-1)^2,x=c_j-1,k=2a_ic_i,b=f_i-a_ic_i^2)。
要使(f_i)尽量大，则(b)要尽量大，所以对于((x,y))我们维护相邻两点斜率递减的上凸壳。
而对于同种颜色，它的斜率(k)必是递增的，所以由斜率优化的那套理论，相邻两点斜率小于(k)的那一段我们不需要，又因为凸壳上斜率递减，那么我们对每种颜色直接维护单调栈，每次取栈顶即为答案。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 1e5 + 5;
int N, a[MAX_N], c[MAX_N], bln[MAX_N];
long long f[MAX_N], X[MAX_N], Y[MAX_N];
long double slope(int i, int j) {
return (long double)(Y[j] - Y[i]) / (X[j] - X[i]);
}
vector<int> q[MAX_N];
int top[MAX_N], mx;
int main () {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
N = gi();
for (int i = 1; i <= N; i++) c[i] = ++bln[a[i] = gi()], mx = max(mx, a[i]);
for (int i = 1; i <= mx; i++) q[i].push_back(0), top[i] = 0;
for (int i = 1; i <= N; i++) {
int col = a[i];
while (top[col] && slope(q[col][top[col] - 1], q[col][top[col]])
<= slope(q[col][top[col]], i)) --top[col];
if ((int)q[col].size() == ++top[col]) q[col].push_back(i);
else q[col][top[col]] = i;
while (top[col] && slope(q[col][top[col] - 1], q[col][top[col]]) <= 2.0 * a[i] * c[i]) --top[col];
int j = q[col][top[col]];
f[i] = f[j - 1] + 1ll * col * (c[i] - c[j] + 1) * (c[i] - c[j] + 1);
X[i + 1] = c[i + 1] - 1, Y[i + 1] = f[i] + 1ll * a[i + 1] * (c[i + 1] - 1) * (c[i + 1] - 1);
}
printf("%lld
", *max_element(&f[1], &f[N + 1]));
return 0;
}