bzoj4709: [Jsoi2011]柠檬 斜率优化

时间：2021-10-12 16:13:16

题目链接

bzoj4709: [Jsoi2011]柠檬

题解

斜率优化

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

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

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

显然这个式子可以斜率优化，整理得：$ac_i 2(c_j - 1) + f_i - a c_i^2 = f_{j-1} + a·(c_j-1)^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\)的最大值，

直接对于每个a_i维护上凸壳。在凸壳上二分。

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

代码

#include<vector>

#include<cstdio>

#include<algorithm>

#define gc getchar()

#define pc putchar

inline int read() {

	int x = 0,f = 1;

	char c = gc;

	while(c < '0' || c > '9') c = gc;

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc;

	return x * f;

}

#define LL long long

void print(LL x) {

	if(x >= 10) print(x / 10);

	pc(x % 10 + '0');

}

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

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

inline LL squ(LL x) {

	return x * x;

}

const int maxn = 1000007;

std::vector<int>v[maxn];

LL f[maxn],a[maxn],c[maxn],cnt[maxn] ;

int main() {

	int n = read();

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

		a[i] = read();

		c[i] = ++ cnt[a[i]];

		int t;

		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);

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

		while(l <= r) {

			int 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))

				ans = mid,l = mid + 1;

			else r = mid - 1;

		}

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

	}

	print(f[n]);

	return 0;

}

/*

5

2 2 5 2 3

*/

相关文章