P4983 忘情

传送门

洛谷

题目背景

“为什么要离开我！”

“因为你没玩儿转！”

“我玩儿转了！”

“那好，你现在就给我维护这么一个式子！”

“为什么要出这么毒瘤的东西。”

“为了恶心你。”

“……”

…………………………….…………………………….

题目描述

你的 $npy$ 为了恶心你，特地请了四位大神和一个辣鸡！

$\rm hdxriehdxrie$ 说：“我们得求和。”于是有了 $\sum \limits_{i=1}^n x_i$ 。

$\rm ImagineImagine$ 说：“我们得有平均数。”于是有了 $\bar x$ 。

$\rm TimeTravellerTimeTraveller$ 说：“我们得有加减乘除。”于是有了一些恶心的组合。

$\rm Althen·Way·SatanAlthen⋅Way⋅Satan$ 说：“我们还得有平方。”于是我们将它平方。

最垃圾的 $\rm ZredXNyZredXNy$ 说：“那我帮你们整合一下。”

于是，我们得到了这么一个式子 :

$\cfrac{\left((\sum\limits_{i=1}^{n}x_i\times \bar x)+\bar x\right)^2}{\bar x^2}$

我们定义一段序列的值为这个，其中 $n$ 为此序列的元素个数。

我们给定一段长度为 $n$ 的序列,现在要求将它分成 $m$ 段，要求每一段的值的总和最小，求出这个最小值。

输入输出格式

输入格式：

第一行两个正整数，分别为 $n$ ， $m$ ，定义见题面。

接下来一行为 $n$ 个正整数，依次给出这个序列的每个元素的值 $x_i$ 。

输出格式：

一个整数，求出这个最小值。

输入输出样例

输入样例#1：

3 2
1 2 3

输出样例#1：

输入样例#2：

10 3
1 2 3 4 5 6 7 8 9 10

输出样例#2：

1140

说明

对于 $30 \%$ 的数据， $m \le n \le500$ ；

另有 $20 \%$ 的数据，保证 $m=2$ ；

对于 $100 \%$ 的数据， $m \le n \le 100000$ ， $1 \le x_i \le 1000$ 。

分析

这种题先看看能不能化简式子。

$\cfrac{\left((\sum\limits_{i=1}^{n}x_i \times \bar x)+\bar x\right)^2}{\bar x^2}$

$\cfrac{\left(\bar x\sum\limits_{i=1}^{n}x_i + \bar x\right)^2}{\bar x^2}$

$\cfrac{\bar x^2\left(\sum\limits_{i=1}^{n}x_i + 1\right)^2}{\bar x^2}$

$\left(\sum\limits_{i=1}^{n}x_i+1 \right)^2$

嗯，斜率优化经典题。
但有个 $m$ 怎么办？
上 $WQS$ 二分。
具体的
然后考虑如何限制段数。感性地理解或者打表观察或者严格的数学证明可以发现：如果我们给每个 $f_i$ 值都强行加上一个 $val$ ，相当于是强行挂了一个重物上去，现在要最小化每个 $f_i$ ，那么你挂的东西越重，为了最小化 $f_i$ 而划分的总段数就会越少。

所以我们可以二分这个重物 $val$ ，斜率优化做一遍 $dp$ ，同时记录一下划分段数 $cnt_i$ ，然后判断划分的总段数 $cnt_n$ 与 $m$ 的大小关系。如果 $cnt_n>m$ 就说明 $val$ 不够大，要调大。
(做法来自GKxx的题解）

参考资料

$WQS$ 二分

Creeper_LKF的关于WQS二分算法以及其一个细节证明

本题题解

GKxx的题解

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 100010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int n,m,Q[maxn],cnt[maxn];
long long s[maxn],f[maxn];
double calc(int a,int b)
{
	return (f[b]+s[b]*s[b]-2*s[b]-f[a]-s[a]*s[a]+2*s[a])/(2.*(s[b]-s[a]));
}
bool check(long long v)
{
	int head=0,tail=0;
	for(int i=1;i<=n;i++)
	{
		while(head<tail&&calc(Q[head],Q[head+1])<=s[i])head+=1;
		f[i]=f[Q[head]]+(s[i]-s[Q[head]]+1)*(s[i]-s[Q[head]]+1)+v;
		cnt[i]=cnt[Q[head]]+1;
		while(head<tail&&calc(Q[tail-1],Q[tail])>=calc(Q[tail],i))tail-=1;
		Q[++tail]=i;
	}
	return cnt[n]>=m;
}
int main()
{
	read(n,m);
	for(int i=1;i<=n;i++)s[i]=s[i-1]+read<int>();
	long long l=0,r=1e16;
	while(l<=r)
	{
		long long mid=(l+r)>>1;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	check(r);
	printf("%lld\n",f[n]-m*r);
    return 0;
}