[bzoj 2726] 任务安排（斜率优化线性dp）

3月14日第三题！！！~~（虽然是15号发的qwq）~~

Description

机器上有N个需要处理的任务，它们构成了一个序列。这些任务被标号为1到N，因此序列的排列为1,2,3…N。这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和。注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。

Input

第一行两个整数，N,S。

接下来N行每行两个整数，Ti,Fi。

Output

一个整数，为所求的答案。

Sample Input

5 1

1 3

3 2

4 3

2 3

1 4

Sample Output

153

HINT

Source

补：范围：

1<=N<=3*10^5,0<=s,ci<=512,-512<=ti<=512.

数据较小版本（n^2即可）请点这：http://blog.csdn.net/ye_xingyu/article/details/79562237

斜率优化，斜率为（s+sumT[i]），当截距最小时的f[i]就是当前最优决策

注意：ti有负数，则sumT[i]不具有单调性要把队列中全部存着（队尾仍可去掉无用决策即不满足下凸性）用二分每次找到左侧斜率小于当前斜率右侧大于的位置，直接用方程转移（即不用min）

code：

//By Menteur_Hxy

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int MAX=300010;

const int INF=0x3f3f3f3f;

int n,s,l,r;

long long ti[MAX],fi[MAX],f[MAX],q[MAX];

//注意开long long 前缀和还是很大的，我因为这个wa两次QAQ

int search(int k) {

    if(l==r) return q[l];

    int L=l,R=r;

    while(L<R) {

        int mid=(L+R)>>1;

        if(f[q[mid+1]]-f[q[mid]]<=k*(fi[q[mid+1]]-fi[q[mid]])) L=mid+1;

        else R=mid;

    }

    return q[L];

}

int main() {

    scanf("%d %d",&n,&s);

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

        scanf("%lld %lld",&ti[i],&fi[i]);

        ti[i]+=ti[i-1];fi[i]+=fi[i-1];

    }

    r=l=1;

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

        int p=search(s+ti[i]);

        f[i]=f[p]-(s+ti[i])*fi[p]+ti[i]*fi[i]+s*fi[n];

        while(l<r && (f[q[r]]-f[q[r-1]])*(fi[i]-fi[q[r]])

            >=(f[i]-f[q[r]])*(fi[q[r]]-fi[q[r-1]])) r--;

        q[++r]=i;

    }

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

    return 0;

}

通过这个题重新复（zi）习(xue)了下斜率优化感觉斜率优化就是来一个维护比值单调的队列（这个值就对应线性规划的坐标系中的斜率）从中选出最优决策。~~（不过感觉弄方程变形又弄变量有点麻烦233~）~~

期待之后有关斜率优化的继续学习与练习(￣▽￣)／。

巴特西

[bzoj 2726] 任务安排（斜率优化线性dp）

最新文章

热门文章

巴特西

[bzoj 2726] 任务安排 （斜率优化 线性dp）

最新文章

热门文章

[bzoj 2726] 任务安排（斜率优化线性dp）