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

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

题面描述

题面

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

       $1\le n\le 10^5，1\le s_i\le 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了。设 $su{m}_i$ 表示 $[1,i]$ 中 $s_i$ 的数量。即 $su{m}_i={\sum }_{j=1}^i[s_j=s_i]$。设 $d{p}_i$ 表示 前 $i$ 个数划分成若干连续段的最大价值和。那么有转移：

       $d{p}_i\leftarrow d{p}_{i-1}+s_i$
       $d{p}_i=\max \left\{d{p}_{j-1}+(su{m}_i-su{m}_j+1{)}^2\times s_i\right\}(s_j=s_i)$

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

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

       $d{p}_i=d{p}_{j-1}+(su{m}_i+1{)}^2\times s_i-2s_i(su{m}_i+1)\times su{m}_j+su{m}_j^2\times s_i$

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

       $d{p}_i=d{p}_{j-1}+(su{m}_i+1{)}^2\times s_i-2s_i(su{m}_i+1)\times su{m}_j+su{m}_j^2\times s_j$

       移项，可得：
       $d{p}_{j-1}+su{m}_j^2\times s_j=2s_i(su{m}_i+1)\times su{m}_j+d{p}_i-(su{m}_i+1{)}^2\times s_i$。

       不难发现这就是 斜率优化 的模型，我们令 $y=d{p}_{j-1}+su{m}_j^2\times s_j，x=su{m}_j$。对于 $i$，斜率 $k$ 是固定的，为 $2s_i(su{m}_i+1)$，$b=d{p}_i-(su{m}_i+1{)}^2\times s_i$。

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

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

       我们可以发现对于一种 $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;
}

这篇关于[JSOI2011] 柠檬（斜率优化DP，优化技巧）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---