一本通提高1607 任务安排2

【题目描述】

有 N 个任务排成一个序列在一台机器上等待执行,它们的顺序不得改变。机器会把这 N 个任务分成若干批,每一批包含连续的若干个任务。从时刻 0 开始,任务被分批加工,执行第i个任务所需的时间是 Ti。另外,在每批任务开始前,机器需要 S 的启动时间,故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。

一个任务执行后,将在机器中稍作等待,直至该批任务全部执行完毕。也就是说,同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 Ci 。

请为机器规划一个分组方案,使得总费用最小。

【输入】

第一行是 N。第二行是 S。

下面 N 行每行有一对正整数,分别为 Ti和 Ci ,表示第 i 个任务单独完成所需的时间是 Ti 及其费用系数 Ci 。

【输出】

一个数,最小的总费用。

【输入样例】

5
1
1 3
3 2
4 3
2 3
1 4

【输出样例】

153

【提示】

数据范围与提示:

对于全部数据,1≤N≤10^4,0≤S≤50,1≤Ti,Ci≤100。

————————————————————————————————————————————

网上大多数都是按照一本通提高篇做的,都是从1到n枚举。我的是逆序枚举的,偏偏做的过程中出了一点点问题,没得参考了,只能自己调。幸好只是小问题!

原先,做过这个题,不过可能是数据较水的问题用任务安排1的代码过了,这次算是正式补上斜率优化这一块!

这个和其他不同的是,就是逆序枚举,还要维护单调性,比较不爽!

————————————————————————————————————————————

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
int n,s;
int f[maxn],sc[maxn],smt[maxn];
int q[maxn],l,r;
ll y(int a)
{
    return f[a]+sc[a]*smt[a];
}
long double get_xl(int a,int b)
{
    return (long double)(y(b)-y(a))/(smt[b]-smt[a]);
}
int main()
{
    scanf("%d%d",&n,&s);
    for(int t,c,i=1;i<=n;++i)
    {
        scanf("%d%d",&smt[i],&sc[i]);
        smt[i]+=smt[i-1];
        sc[i]+=sc[i-1];
    }
    for(int i=n;i>=0;--i)
    {
        while(l<r&&get_xl(q[l],q[l+1])>=sc[i])++l;
        f[i]=f[q[l]]+(sc[q[l]]-sc[i])*smt[q[l]]+(sc[n]-sc[i])*s;
        while(l<r&&get_xl(q[r-1],q[r])<=get_xl(q[r],i))--r;
        q[++r]=i;
    }
    cout<<f[0]<<endl;
    return 0;
}

 

上一篇:kernel都支持smt的cpu的启动


下一篇:医院预约系统小程序源码代码分享