bzoj 4518 征途

Posted on | Edited on | Views:

斜率优化 $dp$ .

  • 推一下式子,记第 $i$ 天走的长度为 $t_i$ , $s=\sum t_i$ ,则 $S^2 \cdot m^2=(m\cdot \sum t_i^2)-s^2$ .

  • 由于 $m,s$ 为定值,所以只需要最小化平方和 $\sum t_i^2$ .

  • 设 $f(i,j)$ 表示走了 $i$ 天,恰好走了 $j$ 段路时的最小平方和, $sum_i$ 表示前 $i$ 段路的长度和.

  • 暴力转移有 $f(i,j)=\min \lbrace f(i-1,k)+(sum_j-sum_k)^2,0\leq k<j \rbrace$ ,可以看出暴力转移是 $O(n^3)$ 的.

  • 若固定 $i$ ,可以看出 $j$ 这一维是满足斜率优化的,因为同时与 $j,k$ 有关的项是 $-2sum_j\cdot sum_k$ ,而 $sum_k$ 单调.

  • 于是就可以进行斜率优化了.若用 $k_1$ 转移比 $k_2$ 更优 ( $k_1>k_2$ ) ,由转移方程可得到:

$$
slope(k_1,k_2)={f(i-1,k_1)+sum_{k_1}^2-f(i-1,k_2)-sum_{k_2}^2 \over sum_{k_1}-sum_{k_2}} < 2sum_j
$$

  • 而斜率 $2sum_j$ 也是单调的,所以并不需要二分,直接暴力跳指针,用单调队列维护下凸壳即可.
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=3e3+10;
int n,m,sum[MAXN],s;
ll f[MAXN][MAXN];
double sqr(double x)
{
	return x*x;
}
double slope(int i,int k1,int k2)
{
	return (f[i-1][k1]+sqr(sum[k1])-f[i-1][k2]-sqr(sum[k2]))/(1.0*sum[k1]-1.0*sum[k2]);
}
int q[MAXN],head,tail;// [head,tail]
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		sum[i]=sum[i-1]+read();
	memset(f,63,sizeof f);
	f[0][0]=0;
	for(int i=1;i<=m;++i)
	{
		head=tail=0;
		for(int j=1;j<=n;++j)
		{
			while(head<tail && slope(i,q[head+1],q[head])<2*sum[j])
				++head;
			int k=q[head];
			f[i][j]=f[i-1][k]+1LL*(sum[j]-sum[k])*(sum[j]-sum[k]);
			while(head<tail && slope(i,q[tail],q[tail-1])>slope(i,q[tail],j))
				--tail;
			q[++tail]=j;
		}
	}
	cout<<f[m][n]*m-1LL*sum[n]*sum[n]<<endl;
	return 0;
}

更了一个用 $WQS$ 二分的做法.

这道题用 $WQS$ 二分,也称凸优化,可以做到 $O(n\log s_n)$ 的时间复杂度.

定义 $g(i)$ 表示必须走 $i$ 段时的最小 $\sum t_j^2$ .那么我们就是要求 $g(m)$ 的值.

普通的斜率优化其实就是在枚举选了多少段.

二分一个权值 $mid$ ,表示每选一段带来的额外花费,此时得到新的函数 $f(x)=g(x)+mid\cdot x$ .

因为 $g(x)$ 是具有凸性的,所以 $g’(x)$ 是单调的,而 $f’(x)=g’(x)+mid$ ,相当于在左右移动 $g’(x)$ 的零点.

而 $f’(x)$ 的零点就是让 $f(x)$ 取得最小值的点,一次斜率 $dp$ 可以 $O(n)$ 求出,也同时求出了 $f(x)$ 的最小值.

通过二分不断调整 $mid$ ,直到 $f’(x)$ 的零点为 $m$ ,就得到了 $f(m)$ ,再根据 $g(m)=f(m)-mid\cdot m$ 得出答案.

因为实际问题中,这些函数只在整数处才有定义,所以二分权值时也只用在整数中二分.

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

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
63
64
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
	int out=0,sgn=1;
	char jp=getchar();
	while(jp!='-' && (jp<'0' || jp>'9'))
		jp=getchar();
	if(jp=='-')
		sgn=-1,jp=getchar();
	while(jp>='0' && jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*sgn;
}
const int MAXN=3e3+10;
ll sqr(ll x)
{
	return x*x;
}
int n,m;
ll f[MAXN],g[MAXN],s[MAXN];
double slope(int k1,int k2)
{
	return (double)(f[k1]+sqr(s[k1])-f[k2]-sqr(s[k2]))/(double)(s[k1]-s[k2]);
}
int q[MAXN],head,tail;
bool check(ll mid)
{
	q[head=tail=0]=0;
	for(int i=1;i<=n;++i)
	{
		while(head<tail && slope(q[head+1],q[head])<2*s[i])
			++head;
		int k=q[head];
		f[i]=f[k]+sqr(s[i]-s[k])+mid;
		g[i]=g[k]+1;
		while(head<tail && slope(q[tail-1],q[tail])>slope(q[tail],i))
			--tail;
		q[++tail]=i;
	}
	return g[n]<=m;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		s[i]=s[i-1]+read();
	ll L=0,R=s[n]*s[n]/m;
	ll res;
	while(L<=R)
	{
		ll mid=(L+R)>>1;
		if(check(mid))
		{
			res=m*(f[n]-mid*m)-sqr(s[n]);
			R=mid-1;
		}	
		else
			L=mid+1;
	}
	cout<<res<<endl;
	return 0;
}