题解 P4072 【[SDOI2016]征途】

· · 个人记录

非常传统的斜率优化题目，当然也是斜率优化里面最简单的一种

如果熟练的话可以很快切掉？

还是先科普一下斜率优化在做什么吧

斜率优化

斜率优化针对的通常是一种解决序列决策问题的dp

这种问题大概是把一个序列拆成m段，每段会产生一定的贡献，现在想最大化/最小化总贡献

然后我们一般来讲通用的dp方程是令dp_{i}表示在i处放置决策点，然后转移的时候暴力枚举上一个端点进行转移

所以转移方程大概会长这样？

dp_{i}=min/max_{k=0}^{i}dp_{k}+cost(i,k)

然后根据问题的不同cost函数会有所变化，当cost比较特殊的时候我们会发现可以使用一种叫做斜率优化的技术来优化转移

那么就以这道题为例讲解斜率优化中最简单的一种——单调队列优化好了

本题题解

首先斜率优化要求我们对待求式进行若干变形

我们先来看一下题目中给出来的式子

最小化(假设走过的第i段路总长为x_i，每条路的长度为a_i)

\frac{\sum_{i=1}^{m}(x_{i}-\bar{x})^{2}}{m}

然后我们做一些简单的代数变换可以得到这个式子

\frac{\sum_{i=1}^{m}x_{i}^{2}-2\bar{x}\sum_{i=1}^{m}x_{i}+m\bar{x}^{2}}{m}

然后我们知道

\bar{x}=\frac{\sum_{i=1}^{m}xi}{m}

代入，得

\frac{m\sum_{i=1}^{m}x_{i}^{2}-(\sum_{i=1}^{m}xi)^2}{m^2}

然后我们最后只需要输出下面这个式子就可以了

m\sum_{i=1}^{m}x_{i}^{2}-(\sum_{i=1}^{n}ai)^2

所以很显然问题变成了最小化\sum_{i=1}^{m}x_{i}^{2}

然后我们发现这是一个序列决策问题，我们令dp_{i,j}表示在i处放下第j个分隔点的最小平方和，那么我们会发现我们的dp方程大概长这样(s(i)表示i的前缀和)

Dp_{i,j}=min_{k=0}^{i}(Dp_{k,j-1}+(s(i)-s(k))^{2})

简单的拆一下式子可以变成

Dp_{i,j}-s^2(i)=min_{k=0}^{i}(Dp_{k,j-1}+s^{2}(k)-s(i)2s(k)

为了方便起见，我们令f(i)=Dp_{i,j}-s^2(i),g(k)=Dp_{k,j-1}+s^{2}(k)

显然我们可以运用高中数学技巧做一个同解变形，变成这样

最大化f(i)

g(k)=s(i)2s(k)+f(i)

我们发现，如果令y=g(k),x=2s(k)的话

我们的dp式子可以看成一个一次函数y=kx+b我们发现对于每一个i，斜率是给定的，此时我们通过将一堆(x,y)代入取b的最大值就可以完成dp了，当然这个标志性的斜率式子也是为什么这种技术被称为斜率优化的原因，把dp的转移关系变成一堆点和一个斜率固定的直线的关系

但是真正重要的是，我们发现求f(i)和f(i-1)时，等待代入的点集只变化了一个点，此时我们通过一些有趣的操作维护这个点集即可完成O(1)的快速转移

具体操作如下：假设我们现在要最大化f(i)

那么我们发现可以使f(i)最大的点k，一定在所有点集的凸包上，更准确的来讲，因为斜率是恒正的(显然前缀和是正的)我们会发现点k一定在下凸壳上

那么让我们来想一想如何维护这个凸包呢？首先一个非常显然的事实是x是单调递增的，(显然前缀和必然单增)此时我们发现可以使用一个双端队列来存这些点，每次我们插入一个点的时候会发现如果这个点和队列的第二个点连接的线使得这个队头凹了进去，我们就可以pop掉这个队头，重复这个过程直到队列里只剩一个点或者形成了一个凸的结构，然后插入这个点

现在凸壳维护好了，我们该如何寻找答案呢？一个性质是在斜率一定的情况下，截距是x的一个单峰函数，我们可以三分……

但是我们发现这样非常不明智，因为我们发现另一个重要性质，斜率也是单增的(显然前缀和单调递增)我们画一个图，发现当斜率单调递增的时候，使f(i)最优的决策点k的x值也是单调递增的，因此我们可以贪心的比较当前队尾计算的答案和第二个队尾的答案是否更优，如果第二个队尾的答案更优那么我们就pop队尾，因为斜率递增，被pop的点再也不会作为最优的决策点

所以我们只需要写一个单调队列维护这个凸包就可以了，然后每次贪心的进行pop队尾，取最优解即可

然后求出f(i)之后可以解出dp(i)，当这一轮的dp完毕之后，我们以这一轮的dp值计算出下一轮要用的y即可，x在每一轮都是不变的所以不用管他

几个trick，单调队列可以只存点的编号，这样的话我们重新修改y值的时候非常好修改

然后记得求出来的f(i)不是dp值，记得加上一个s^2(i)才是

然后求出来了dp值并不是结束，还要乘上一个m再减去一个s^2(n)才是答案

说了这么多其实代码超级短~

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=3*1e3+10;
int n;int m;typedef double db;typedef long long ll;
ll dp[N];ll q[2*N];ll x[N];ll y[N];int hd;int tl;//计算斜率 
inline db ck(int p,int q){db ret=(db)(y[p]-y[q])/(db)(x[p]-x[q]);return ret;}
inline ll ca(int p,ll k){ll ret=y[p]-k*x[p];return ret;}//计算答案 
ll sum[N];
int main()
{
    scanf("%d%d",&n,&m);//求sum 
    for(int i=1;i<=n;i++){scanf("%d",&sum[i]);sum[i]+=sum[i-1];}
    for(int i=1;i<=n;i++){x[i]=2*sum[i];}//计算x 
    for(int i=1;i<=n;i++){y[i]=2*sum[i]*sum[i];}//计算最开始的y 
    for(int z=2;z<=m;z++)//一共进行m-1轮 
    {
        hd=1;tl=0;//清空双端队列 
        for(int i=1;i<=n;i++)
        {
            for(;tl-hd>0&&ck(i,q[tl])<ck(i,q[tl-1]);tl--);q[++tl]=i;//插入一个点 
            for(;tl-hd>0&&ca(q[hd],sum[i])>ca(q[hd+1],sum[i]);hd++);//计算最优解 
            dp[i]=ca(q[hd],sum[i])+sum[i]*sum[i];//计算dp值 
        }
        for(int i=1;i<=n;i++){y[i]=dp[i]+sum[i]*sum[i];}//统一更新y 
    }printf("%lld",m*dp[n]-sum[n]*sum[n]);return 0;//拜拜程序~ 
}