[LOJ10186]任务安排

试题分析

一道斜率优化的dp

易得方程$f[j]=(S+t[i])\times c[j]+f[i]-t[i]\times c[i]+s\times c[n]$,为什么要写成这要，因为这样其实就可以将$min$拆掉，并且是一个函数形式，$(S+t[i])$为斜率，$f[i]-t[i]\times c[i]+s\times c[n]$为截距。

并且当我们要决策$i$用哪一个j时，我们会发现斜率是一样的,就只有截距会不同。所以我们要让截距越短。

所以发现当斜率为上升时，即为下凸壳的形式，所以我们可以用单调队列去优化

但是$t$有可能是负数，我们将线进行平移的时候要保证此点之前的斜率都小于$k$,之后全大于$k$,所以需要二分找到此区间

20181216 update:

为什么当截距最短是会取到$min{f[i]}$,因为$f[i]-t[i]\times c[i]+s\times c[n]$这个式子中$-t[i]\times c[i]+s\times c[n]$是定值，而又因为$f[i]$是$+f[i]$，所以只需要维护最小值即可。

但当截距出现$-f[i]$时，就必须让截距最大了，要维护的是一个上凸壳。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<climits>

#define int long long

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int N=;

int l,r,num[N];

int f[N],t[N],c[N],S,n,que[N];

int query(int pos,int X){

    int L=l,R=r,maxn=;

    int mid;

    while(L<=R){

        mid=L+R>>;

        if(f[que[mid+]]-f[que[mid]]<=X*(c[que[mid+]]-c[que[mid]])) L=mid+,maxn=max(maxn,mid);

        else R=mid-;

    }

    return que[maxn+];

}

signed main(){

    n=read(),S=read();

    for(int i=;i<=n;i++) t[i]=t[i-]+read(),c[i]=c[i-]+read();

    l=,r=;f[]=;

    for(int i=;i<=n;i++){

        int H=query(i,S+t[i]);

        f[i]=f[H]-(S+t[i])*c[H]+t[i]*c[i]+S*c[n];

        while(l<r&&(f[que[r]]-f[que[r-]])*(c[i]-c[que[r]])>=(f[i]-f[que[r]])*(c[que[r]]-c[que[r-]])) r--;

        que[++r]=i;

    }printf("%lld\n",f[n]);

    return ;

}

巴特西

[LOJ10186]任务安排

试题分析

最新文章

热门文章