斜率优化学习笔记

~~（解释太麻烦，这里笼统的讲一下，具体看书，书上更详尽，所以无视这部分）~~

斜率优化通常一般可以将(n^2)的DP优化到(O(n)) ，是一个很强的优化。

形如：

[f[i]=min{f[j]+(s[i]-s[j])^2}(i-dleq j) ]

看似好像可以用单调队列的，但是无法把(i,j)分开的DP，大部分可以用斜率优化；

一般斜率优化具有单调性，可以用单调队列维护有效决策；

单调性什么意思？有效决策什么意思？

例如这个方程，把它变一下，把(min)去掉，把关于(j)的都移到左边，关于(i)和(i,j)的移到右边：

[f[j]+s[j]^2=2*s[i]*s[j]+f[i]-s[i]^2 ]

(s[i])都是已知的，要在一堆({f[j],s[j]})中选出一个使得(f[i])最小；

那么对于每一个({f[j],s[j]}) ，放在平面直角坐标系中设(f[j]+s[j]^2)为(y) ，(s[j])为(x) ，可以画出一条斜率为(2*s[i])的直线，那么这条线的截距就为(f[i]-s[i]^2) ；

那么使得截距最小的({f[j],s[j]}) 就为所求。

所以决策就是这些({f[j],s[j]}) ，而有效决策就是对求(f[i])有贡献的决策。

这里(s[i])单调递增，就因为着斜率单调递增，每次新加入的决策也在最右边。

然后结合书上讲的有些关于凹凸的东西，直线平移，什么的，看书。~~（滑稽）~~

（ps: 加黑的都是斜率优化的套路）

列出斜率方程后就基本上可以直接套板子了；

任务安排2

一开始想到暴力DP方程：(设(f[i][j])为前(j)个任务分为(i)批的最小费用,(sum)为各种前缀和)

[f[i][j]=min{f[i-1][k]+(S*i+sumT[j])*(sumC[j]-sumC[k])} ]

拆开也是可以斜率优化的，因为拆开后只会得到一项(j,k)无法分开的，这是可以套板子的，但是(i)是没有限制的，所以难以得出答案；

那么考虑当每分一个组的时候后面的时间都会往后移(S) ，那么最后总费用就会增加(S*(sumC[n]-sumC[j])) ，那就好办了，设(f[i])为前(i)个任务的最小费用，就有状态转移方程：

[f[i]=min{f[j]+sumT[i]*(sumC[i]-sumC[j])+S*(sumC[n]-sumC[i])} ]

其实这里(f[i])的定义有误，应该为前(i)个任务对最后答案的最小贡献。（无视这句话也可以写）

转化为斜率方程：

[f[j]=(S+sumT[i])*sumC[j]+f[i]-sumT[i]*sumC[i]-S*sumC[n] ]

这里斜率和加入点的横坐标是单调递增的，然后又可以开心的套板子了。

任务安排3

和上题不一样的地方就是列出的斜率方程，斜率没有单调性，但是有效决策的横坐标的加入还是单调递增的，那就二分查找最优的决策就可以了。

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=3e5+5;
ll f[N],n,s;
ll sumc[N],sumt[N];
ll head=1,tail=1;
ll q[N];
ll read()
{
    ll f=1;
    char ch;
    while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
    ll res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
    return res*f;
}
ll check(int i)
{
    if(head==tail) return q[head];
    int l=head,r=tail;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(f[q[mid+1]]-f[q[mid]]<=(s+sumt[i])*(sumc[q[mid+1]]-sumc[q[mid]])) l=mid+1;
        else r=mid;
    }
    return q[r];
}
void solve(int i)
{
    ll j=check(i);
    f[i]=f[j]-(s+sumt[i])*sumc[j]+sumt[i]*sumc[i]+sumc[n]*s;
    while(head<tail&&(f[i]-f[q[tail]])*(sumc[q[tail]]-sumc[q[tail-1]])<=(f[q[tail]]-f[q[tail-1]])*(sumc[i]-sumc[q[tail]])) tail--;
    q[++tail]=i;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("task.in","r",stdin);
    freopen("task.out","w",stdout);
#endif
    n=read(),s=read();
    for(int i=1;i<=n;i++)
    {
        ll t=read(),c=read();
        sumt[i]=sumt[i-1]+t;
        sumc[i]=sumc[i-1]+c;
    }
    for(int i=1;i<=n;i++) solve(i);
    printf("%lld
",f[n]);
    return 0;
}

Cats Transport

这题有个巧妙的思路~~（巧妙的思路当然不是我想出来的啊）~~设(a[i]=t[i]-sum_{j=1} ^i d[j]) ，这样就可以表示出如果饲养员要接到第(i)只猫就要在(a[i])之后出发，且猫(i)等待的时间为(t-a[i]) ；

那么这样就好办了，只要将(a[i])从小到大排序，求出前缀和(suma[i])，那要带走区间([l+1,r])的猫，这些猫要等待待的时间为(a[r]*(r-l)-(suma[r]-suma[l])) 。

这样就有状态转移方程：

[f[i][j]=min{f[i-1,k]+a[j]*(j-k)-(suma[j]-suma[k])} ]

玩具装箱

直接划分就好了，设(f[i])为前(i)个的最小价值，(Sum[i])为加上了填充物之后的长度的前缀和，即(Sum[i]=Sum[i-1]+c[i]+1) ，这样就有DP方程：

[f[i]=min{f[j]+(Sum[i]-(Sum[j]+1)-L)^2} ]

为了简化式子，再设(S[j]=Sum[j]+1) ，然后去掉(min)把这个式子变为斜率优化通常的亚子：

[f[j]+S[j]^2+2*L*S[j]=2*Sum[i]*S[j]+f[i]-(Sum[i]-L)^2 ]

然后以此建立坐标系，方程左边为(y) ，(S[j])为(x) ，然后每条线斜率为(2*Sum[i]) ，

仓库建设

为了把最后得到的斜率方程使得斜率和(x)都单调递增，我尝试了一堆表示方法~~（甚至一度怀疑是不是又要二分了）~~，不过最后还是在我不懈的努力下列出来了~~（哭泣）~~

由题意可得最后一个工厂一定要设置仓库，所以可以设(f[i])为前(i)个工厂的最小花费，且第(i)个工厂建设仓库，这样(f[n]) 就是最后的答案；

下面就是我想了很久的东西了：（ps：(d[i])为题目中的(x[i])）

对于每个工厂，(d[i]*p[i])为每个工厂送到工厂1所需要的费用，那么设(sumf[i])为这费用的前缀和，然后再设(sump[i])为(p[i])的前缀和，所以对于区间([l,r])的物品全部运到(r)所需要的费用为(d[r]*(sump[r]-sump[l])-(sumf[r]-sumf[l])) ，可以通过画图理解；

所以有状态转移方程：

[f[i]=min{f[j]+d[i]*(sump[i]-sump[j])-(sumf[i]-sumf[l])+c[i]} ]

变成斜率优化的方程，把关于(j)的都移到左边，关于(i)和(i,j)的移到右边：

[f[j]+sumf[j]=d[i]*sump[j]+f[i]-d[i]*sump[i]+sumf[i]-c[i] ]

斜率为(d[i]) ，(x)为(sump[j]) ，他们都单调递增，那就写完了，套板子就好了。

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e6+5;
int n;
ll sumf[N],sump[N],d[N],c[N],f[N];
ll q[N],x[N],y[N];
ll read()
{
    ll f=1;
    char ch;
    while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
    ll res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
    return res*f;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("publi.in","r",stdin);
    freopen("publi.out","w",stdout);
#endif
    n=read();
    for(int i=1;i<=n;i++)
    {
        d[i]=read();
        ll p=read();
        c[i]=read();
        sumf[i]=sumf[i-1]+d[i]*p;
        sump[i]=sump[i-1]+p;
    }
    int head=1,tail=1;
    for(int i=1;i<=n;i++)
    {
        while(head<tail&&(y[head+1]-y[head])<=d[i]*(x[head+1]-x[head])) head++;
        f[i]=f[q[head]]+d[i]*(sump[i-1]-sump[q[head]])-(sumf[i-1]-sumf[q[head]])+c[i];
        while(head<tail&&(f[i]+sumf[i]-y[tail])*(x[tail]-x[tail-1])<=(y[tail]-y[tail-1])*(sump[i]-x[tail])) tail--;
        q[++tail]=i,y[tail]=f[i]+sumf[i],x[tail]=sump[i];
    }
    printf("%lld",f[n]);
    return 0;
}

特别行动队

与前几题不也一样的地方就是斜率递减，但(x)还是递增；还是可以用单调队列，维护一个单调递减的斜率；在匹配斜率的时候只需要找到一个斜率比它小的就可以了；

DP方程：

[f[i]=max{f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c} ]

后面还是板子；

打印文章

板子；

锯木厂选址

和仓库建设类似，不过更简单，先(O(n))算出第一个锯木厂对于前(i)颗树的最优策略，然后求二个锯木厂最优策略就和仓库建设的思路一样了，最后再(O(n))枚举一下第二个锯木厂的位置，后面的都运到山底去，取个(min)就完事了；

任务安排4

以后要写的题。

点的加入和斜率都不具有单调性，需要动态加点，那就需要平衡树维护，具体怎么操作，这里留个坑，等我写完了再补回来。