P4983 忘情

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 3.1k | 阅读时长 ≈ 3 分钟

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$ 说：“那我帮你们整合一下。”

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

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

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

3 2
1 2 3

输出样例#1：

32

输入样例#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$。

分析

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

嗯，斜率优化经典题。
但有个$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的题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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;
}