BZOJ1911 [Apio2010]特别行动队 - 动态规划 - 斜率优化

时间:2022-02-18 19:28:15

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门

UPD(2018-04-01):用Latex重打了公式……

题意概括

把一个整数序列划分成任意连续的段,使得划分出来的每一段的价值和最大。

对于某一段,价值的计算公式为 $V=ax^2+bx+c$,其中 $x$ 为当前段的数值和。

题解

这题是博主大蒟蒻的第一道斜率优化DP题……

C++:while (1) 懵逼++;

Pascal:while (true) do inc(懵逼);

本题首先一看就是 DP 题。

但是一看 $1\leq n\leq 1000000,-5\leq a\leq -1,|b|\leq 10000000,|c|\leq 10000000,1\leq xi\leq 100$

彻底吓懵!

一脸懵逼……

还是一脸懵逼……

突(bai)然(du)发(yi)现(xia)可以用斜率优化。

为了减少代码量,好心的出题人特意规定了$-5\leq a\leq -1$

我们来考虑一下:

用 $dp_i$ 表示划分到前$i$个所能得到的最大价值和。

我们设 $sum_i$ 为前$i$个的前缀和,

那么

$$dp_i=max\{dp_j+a(sum_i-sum_j)^2+b(sum_i-sum_j)+c\}  (0\leq j<i)$$

貌似是一个$n^2$的状态转移方程。

其实就是一个$n^2$的状态转移方程。

接下来就是斜率优化了!

我们假设对于$dp_i$来说,从$j$转移比从$k$转移更优秀($j>k$),那么有如下的表达式:

$$dp_j+a(sum_i-sum_j)^2+b(sum_i-sum_j)+c>dp_k+a(sum_i-sum_k)^2+b(sum_i-sum_k)+c$$

so

$$dp_j+a(sum_i-sum_j)^2+b(sum_i-sum_j)>dp_k+a(sum_i-sum_k)^2+b(sum_i-sum_k)$$

$$dp_j+a\cdot sum_i^2-2a\cdot sum_isum_j+a\cdot sum_j^2+b\cdot sum_i-b\cdot sum_j>dp_k+a\cdot sum_i^2-2a\cdot sum_isum_k+a\cdot sum_k^2+b\cdot sum_i-b\cdot sum_k$$

$$dp_j-2a\cdot sum_isum_j+a\cdot sum_j^2-b\cdot sum_j>dp_k-2a\cdot sum_isum_k+a\cdot sum_k^2-b\cdot sum_k$$

$$(dp_j+a\cdot sum_j^2-b\cdot sum_j)- (dp_k+a\cdot sum_k^2-b\cdot sum_k)>2a\cdot sum_i(sum_j-sum_k)$$

so

$$\frac{(dp_j+a\cdot sum_j^2-b\cdot sum_j)-(dp_k+a\cdot sum_k^2-b\cdot sum_k)}{sum_j-sum_k}>2a\cdot sum_i$$

我们设$x_p=sum_p,y_p=dp_p+a\cdot sum_p^2-b\cdot sum_p$,

那么原来的方程可以表示为:

$$\frac{y_j-y_k}{x_j-x_k}>2a\cdot sum_i$$

左边不就是斜率的表达式吗!!

所以叫斜率优化。

当然前面的只是一些化简,关键是接下来的:

我们设$g_{i,j}=\Large\frac{y_i-y_j}{x_i-x_j}$

注意$a$是一个负数,而且$sum_i$是随着$i$的增大而增大的,所以$2a\cdot sum_i$一定是单调递减的!

如果$g_{i,j}>g_{j,k}$那么决策$j$一定是没用的!$(k<j<i)$

分两种情况进行讨论:

1. 如果$g_{i,j}>2a\cdot sum_x$,那么说明决策$i$优于决策$j$,那么$j$就是没用的。就算以后$2a\cdot sum_x$会变,$x$只能变大,所以 $2a\cdot sum_x$也只能变小,所以该表达式仍然满足。

2. 如果$g_{i,j}<2a\cdot sum_x$,那么$g_{j,k}<2a\cdot sum_x$,那么$j$就会比$k$劣,同样也会把$j$扔掉。

然后我们单调队列弄几下就好了。

在$dp$的过程中,按照“如果$g_{i,j}>g_{j,k}$那么决策$j$一定是没用的!”的规则入队,按照 如果$g_{i,j}>2a\cdot sum_x$的规则出队即可。

代码

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=+;
int n,head,tail;
LL a,b,c,r[N],sum[N],x[N],y[N],dp[N],q[N];
double g(int i,int j){
double xi=x[i],xj=x[j],yi=y[i],yj=y[j];
return (yi-yj)/(xi-xj);
}
int main(){
scanf("%d%lld%lld%lld",&n,&a,&b,&c);
sum[]=;
for (int i=;i<=n;i++)
scanf("%lld",&r[i]),sum[i]=sum[i-]+r[i];
memset(x,,sizeof x);
memset(y,,sizeof y);
head=,tail=;
q[++tail]=;
for (int i=;i<=n;i++){
while (head+<=tail&&g(q[head],q[head+])>*a*sum[i])
head++;
LL s=sum[i]-sum[q[head]];
dp[i]=dp[q[head]]+a*s*s+b*s+c;
x[i]=sum[i],y[i]=dp[i]+a*sum[i]*sum[i]-b*sum[i];
while (head+<=tail&&g(q[tail-],q[tail])<g(q[tail],i))
tail--;
q[++tail]=i;
}
printf("%lld",dp[n]);
return ;
}