最大K段和

题目大意

有一个长度为 (N) 的序列 (A) 。他希望从中选出不超过 (K) 个连续子段，满足它们两两不相交，求总和的最大值（可以一段也不选，答案为 (0)）。

分析

很容易想到 (O(n^2)) 的 (dp)
设 (f[i][j]) 表示选到第 (i) 位，已选了 (j) 段时的最大答案
那么 (f[i][j] = max(f[i-1][j] ， s[i] + max_limits{0<l<i}(f[l][j-1] - s[l])))
然后维护最大的 (f[l][j-1]-s[l]) ，(O(1)) 更新即可
然后我们可以想到 (WQS) 二分（虽然我想不到）
它大概就是解决：有 (n) 个带权物品，用满足一定限制的方法选 (m) 个，使得其权值和取最值，而且权值和的最值是关于 (m) 的凸函数
注意 (x) 是段数
用直线 (y=kx + b) 去切
因为我们要求最大值，所以要最大化 (b)
(b=y-kx)
那么我们就可以将原来的 (dp) 是改为
(f[i]=max(f[i-1] ， s[i] - k + max_limits{0<l<i}(f[l]-s[l])))

总的来说，先二分 (k)，然后判断就 (dp)，并记录所分的段数
段数恰为 (m) 时就为答案
注意最后要以 (k=ans) 再 (dp) 一遍

(Code)

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;

const int N = 1e5 + 5;
int n , k , a[N];
LL f[N] , g[N] , s[N] , l , r , mid , ans;

bool check()
{
	int x = 0;
	for(register int i = 1; i <= n; i++)
	{
		f[i] = f[i - 1] , g[i] = g[i - 1];
		if (f[x] + s[i] - s[x] - mid > f[i])
			f[i] = f[x] + s[i] - s[x] - mid , g[i] = g[x] + 1;
		if (f[i] - s[i] > f[x] - s[x]) x = i;
	} 
	return g[n] >= k;
}

int main()
{
	freopen("maxksum.in" , "r" , stdin);
	freopen("maxksum.out" , "w" , stdout);
	scanf("%d%d" , &n , &k);
	for(register int i = 1; i <= n; i++) 
		scanf("%d" , &a[i]) , s[i] = s[i - 1] + a[i];
	r = 0x3f3f3f3f3f3f3f3f;
	while (l <= r)
	{
		mid = (l + r) >> 1;
		if (check()) ans = mid , l = mid + 1;
		else r = mid - 1;
	}
	mid = ans , check();
	printf("%lld" , f[n] + ans * k);
}