【bzoj4709】[Jsoi2011]柠檬斜率优化

题目描述

给你一个长度为 $n$ 的序列，将其分成若干段，每段选择一个数，获得 $这个数\times 它在这段出现次数的平方$ 的价值。求最大总价值。

$n\le 10^5$ 。

输入

第 1 行：一个整数，表示 N。

第 2 .. N + 1 行：每行一个整数，第 i + 1 行表示 si。

输出

仅一个整数，表示 Flute 最多能得到的柠檬数。

样例输入

5
2
2
5
2
3

样例输出

题解

斜率优化

设 $f[i]$ 表示前 $i$ 个数分成若干段的最大总价值。

显然对于分成的每一段，左端点的数、右端点的数、选择的数一定是相同的。因为如果不相同则可以从这个段里删去这个数，答案会更优。

于是就有转移：$f_i=f_{j-1}+a·(c_i-c_j+1)^2\ ,\ j\le i\ ,\ a_j=a_i$ ，其中 $a$ 表示原序列，$c$ 表示这个位置时这个数第几次出现（即出现次数的前缀和）。

显然这个式子可以斜率优化，整理得：$f_{j-1}+a·(c_j-1)^2=ac_i·2(c_j-1)+f_i-ac_i^2$ ，其中 $y$ 是 $f_{j-1}+a·(c_j-1)^2$ ，$k$ 是 $ac_i$ ，$x$ 是 $2(c_j-1)$ ，$b$ 是 $f_i-ac_i^2$ 。

这里 $k$ 单调递增，$x$ 单调递增，然而要求的是 $b$ 的最大值，因此只能使用单调栈维护上凸壳。对每种数开一个vector即可。询问时在vector上二分。

时间复杂度 $O(n\log n)$

#include <cstdio>

#include <vector>

#define N 100010

#define y(i) (f[i - 1] + a[i] * squ(c[i] - 1))

#define x(i) 2 * (c[i] - 1)

using namespace std;

typedef long long ll;

vector<int> v[10010];

ll cnt[10010] , c[N] , f[N];

int a[N];

inline ll squ(ll x)

{

	return x * x;

}

int main()

{

	int n , i , l , r , mid , ret , t;

	scanf("%d" , &n);

	for(i = 1 ; i <= n ; i ++ )

	{

		scanf("%d" , &a[i]) , c[i] = ++cnt[a[i]];

		while((t = v[a[i]].size() - 1) > 0 && (x(i) - x(v[a[i]][t])) * (y(v[a[i]][t - 1]) - y(v[a[i]][t])) - (y(i) - y(v[a[i]][t])) * (x(v[a[i]][t - 1]) - x(v[a[i]][t])) > 0) v[a[i]].pop_back();

		v[a[i]].push_back(i);

		l = 1 , r = v[a[i]].size() - 1 , ret = 0;

		while(l <= r)

		{

			mid = (l + r) >> 1;

			if(f[v[a[i]][mid] - 1] + a[i] * squ(c[i] - c[v[a[i]][mid]] + 1) > f[v[a[i]][mid - 1] - 1] + a[i] * squ(c[i] - c[v[a[i]][mid - 1]] + 1)) ret = mid , l = mid + 1;

			else r = mid - 1;

		}

		f[i] = f[v[a[i]][ret] - 1] + a[i] * squ(c[i] - c[v[a[i]][ret]] + 1);

	}

	printf("%lld\n" , f[n]);

	return 0;

}

巴特西

【bzoj4709】[Jsoi2011]柠檬斜率优化

最新文章

热门文章

巴特西

【bzoj4709】[Jsoi2011]柠檬 斜率优化

最新文章

热门文章

【bzoj4709】[Jsoi2011]柠檬斜率优化