[JSOI2011] 柠檬（斜率优化DP，优化技巧）

本文主要是介绍[JSOI2011] 柠檬（斜率优化DP，优化技巧），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面描述

题面

简要题意：
给出一个长度为 $n$ 的整数序列 $s_i$ 。可以将序列任意划分成若干非空连续段。对于每一段，可以选择一个整数 $s_0$ ，若该段 $s_0$ 的数量为 $t$ ，则该段的价值为 $s_0 \times t^2$ 。请求出每一段价值之和的最大值。

$\leq n \leq 10^5，1 \leq s_i \leq 10^4$ 。

分析

我们首先考虑怎样的一段才可能成为答案划分的一部分。如果区间 $[l, r]$ 为一个连续段，那么我们设选出的整数为 $s_0$ 。容易想到 $s_l = s_0$ 。因为如果 $s_l \ne s_0$ ，那么我们把 $s_l$ 单独划分成一段， $[l + 1, r]$ 划分成一段，答案会更优。因为 $[l + 1, r]$ 与之前答案一样，新增出来的一段 $[l, l]$ 会多一个 $s_l$ 的贡献。进一步思考，我们能够发现 $s_r = s_0$ 。这个性质和上面的类似，不再证明。
因此我们明白了，对于一个区间 $[l, r]$ ，它能够成为答案的一个连续段， 当且仅当 $s_l = s_r$ ，并且此时连续段选出的整数 $s_0 = s_l$ 。

基于这个性质，我们就可以dp了。设 $sum_i$ 表示 $[1, i]$ 中 $s_i$ 的数量。即 $sum_i = \sum_{j = 1}^{i}[s_j = s_i]$ 。设 $dp_i$ 表示 前 $i$ 个数划分成若干连续段的最大价值和。那么有转移：

$dp_{i} \gets dp_{i - 1} + s_i$
$dp_{i} = \max\left \{ dp_{j - 1} + (sum_{i} - sum_{j} + 1)^2 \times s_i \right \}(s_j = s_i)$

第一个转移式是简单的，但是第二个转移复杂度达到了 $O(n^2)$ 。我们考虑优化。

观察可以发现第二个式子有点像 斜率优化，我们把式子展开进行观察。

$dp_{i} = dp_{j - 1} + (sum_i + 1)^2 \times s_i - 2s_i(sum_i + 1) \times sum_j + sum_j^2 \times s_i$

由于 $s_i = s_j$ ，我们 把第四项中的 $s_i$ 换成 $s_j$ 。

$dp_i = dp_{j - 1} + (sum_i + 1)^2 \times s_i - 2s_i(sum_i + 1) \times sum_j + sum_j^2 \times s_j$

移项，可得：
$dp_{j - 1} + sum_{j}^2 \times s_j = 2s_i(sum_i + 1) \times sum_{j} + dp_{i} - (sum_i + 1)^2 \times s_i$ 。

不难发现这就是 斜率优化 的模型，我们令 $dp_{j - 1} + sum_{j}^2 \times s_j， x = sum_j$ 。对于 $i$ ，斜率 $k$ 是固定的，为 $2s_i(sum_i + 1)$ ， $dp_i - (sum_i + 1)^2 \times s_i$ 。

由于 $(sum_i + 1)^2 \times s_i$ 是一个定值，我们只需要让 $b$ 最大即可。那么我们对不同的 $s$ 值分别维护上凸包，每次二分查找 第一个 斜率小于当前 $k$ 的点，然后 $O (1)$ 转移即可。时间复杂度 $O(nlog_2n)$ 。

等等！！！难道这样就结束了吗？

我们可以发现对于一种 $s$ 值，从前往后斜率是 单调递增 的。但我们要维护的是 上凸包，好像不能弹出每次 弹出队头 。但是可以发现，队列中斜率是单调递减的，如果当前队尾不能转移给 $i$ ，那么它以后也不可能成为转移项，因此直接弹出队列就行了。也就是说，对于每一个 $i$ ，我们从 $s_i$ 的队列中从队尾往前扫，如果队尾上一个元素与队尾的斜率小于等于 $k$ ，那么直接弹出队尾。否则拿出队尾进行转移就好了。时间复杂度 $O (n)$ 。

CODE：

#include<bits/stdc++.h> // 性质：区间 [l, r] 会成为划分的一部分当且仅当 sl = sr
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, pos[N];
LL dp[N], sum[N], a[N];
inline LL Y(int x) {return dp[x - 1] + sum[x] * sum[x] * a[x];}
inline LL X(int x) {return sum[x];}
vector< int > q[N];
int main() {scanf("%d", &n);for(int i = 1; i <= n; i ++ ) {scanf("%lld", &a[i]);sum[i] = sum[pos[a[i]]] + 1;pos[a[i]] = i;}for(int i = 1; i <= n; i ++ ) {dp[i] = dp[i - 1] + a[i]; // 基础转移int p = q[a[i]].size() - 1;while(p > 0 && (Y(q[a[i]][p]) - Y(q[a[i]][p - 1])) <= (X(q[a[i]][p]) - X(q[a[i]][p - 1])) * (2LL * a[i] * (sum[i] + 1LL))) p --, q[a[i]].pop_back(); // 斜率单增int j = (p == -1 ? -1 : q[a[i]][p]);if(j != -1) dp[i] = max(dp[i], dp[j - 1] + (sum[i] - sum[j] + 1LL) * (sum[i] - sum[j] + 1LL) * a[i]);while(p > 0 && (Y(i) - Y(q[a[i]][p])) * (X(q[a[i]][p]) - X(q[a[i]][p - 1])) >= (Y(q[a[i]][p]) - Y(q[a[i]][p - 1])) * (X(i) - X(q[a[i]][p]))) p --, q[a[i]].pop_back();q[a[i]].push_back(i);}printf("%lld\n", dp[n]);return 0;
}