Steven_MengのBlog

首先上一道例题:

HDU3507

给你一个序列,你可以把这个序列分成若干段,每段的花费是$(\sum _{i=1} ^k C[i])^2 +M$

考虑朴素的$n^2$方程,$dp[i]=\min(dp[j]+M+(sum[i]-sum[j])^2)$

其中$sum[i]$为$C[i]$的前缀和。

发现这个算法的瓶颈在寻找最优的$j$,如果我们可以$O(1)$的找到$j$,那么整个算法的时间复杂度为$O(n)$,可以AC。

考虑两个数$j_1,j_2$,$j_1>j_2$,考虑$j_1$比$j_2$更优的条件:

$dp[j_1]+M+(sum[i]-sum[j_1])^2<dp[j_2]+M+(sum[i]-sum[j_2])^2$

移项,此处省略1w字,得:

$dp[j_1]-dp[j_2]+sum[j_1]^2-sum[j_2]^2<2 \times sum[i] \times (sum[j_1]-sum[j_2])$

不妨设$y(i)=dp[i]+sum[i]^2$,$x(i)=sum[i]$

原式化为以下形式:

$y(j_1)-y(j_2)<2 \times sum[i] \times (x(j_1)-x(j_2))$

发现这个其实类似于斜率:

$\dfrac{y(j_1)-y(j_2)}{x(j_1)-x(j_2)} < 2 \times sum[i]$

其中我们能做这样的变换,有一个重要的先决条件,即$x(j_1)>x(j_2),j_1>j_2$

将$x,y$表示在二维平面上面,如图:

用一个斜率为$2 \times sum[i]$的直线去逼近,发现切点就是最佳决策,又发现$2 \times sum[i]$随着$i$的增大而增大,所以之前舍弃的决策点不可能成为下一步的最佳决策点,于是我们可以用一个单调队列维护决策点集合。

1
2
3
4
inline double Slope(int i,int j){
return (double)(dp[i]+sum[i]*sum[i]-dp[j]-sum[j]*sum[j])/(double)(sum[i]-sum[j]);
}
while (head<rear&&Slope(q[head+1],q[head])<=(double)2.00*sum[i]) head++;

如何插入元素呢,我们像凸包一样插入和删除,如图:

1
2
while (head<rear&&Slope(q[rear],q[rear-1])>=Slope(i,q[rear])) rear--;
q[++rear]=i;

想学习凸包可以参考这篇博客

代码实现(还是很简短的):

注意此代码精度有问题,你们可以把除法改成乘法试一下。

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
#include <bits/stdc++.h>
#define MAXN 1000005
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1ll;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3ll)+(x<<1ll)+(ch^'0');
ch=getchar();
}
return x*f;
}
int sum[MAXN];
int dp[MAXN],q[MAXN],head,rear;
inline double Slope(int i,int j){
return (double)(dp[i]+sum[i]*sum[i]-dp[j]-sum[j]*sum[j])/(double)(sum[i]-sum[j]);
}
#undef int
int main(){
#define int long long
int n,M;
while (~scanf("%lld%lld",&n,&M)){
memset(sum,0,sizeof(sum));
for (register int i=1;i<=n;++i){
int x;
scanf("%lld",&x);
sum[i]=sum[i-1]+x;
}
memset(dp,0,sizeof(dp));
memset(q,0,sizeof(q));
head=1,rear=1;
q[1]=0;
for (register int i=1;i<=n;++i){
while (head<rear&&Slope(q[head+1],q[head])<=(double)2.00*sum[i]) head++;
int j=q[head];
dp[i]=dp[j]+M+(sum[i]-sum[j])*(sum[i]-sum[j]);
while (head<rear&&Slope(q[rear],q[rear-1])>=Slope(i,q[rear])) rear--;
q[++rear]=i;
}
printf("%lld\n",dp[n]);
}
}

图片转自csdn

注意到普通斜率优化的条件是斜率单调,$x$坐标单调,但是对于更一般的情况,就发现普通斜率优化会咕咕,这时候我们要使用CDQ分治优化斜率优化,可以参考这篇博客学习一下。

 评论