BZOJ 2726: [SDOI2012]任务安排 [斜率优化DP 二分提前计算代价]

2726: [SDOI2012]任务安排

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 868 Solved: 236
[Submit][Status][Discuss]

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

时间有负数？！

状态方程张这模样的题一般就用斜率优化(f[i]=f[j]+(j+1...i+什么东西)*什么东西)

如何计算代价？

最烦的就是s了，于是可以提前计算s对后面造成的代价

{类似题目：http://www.cnblogs.com/candy99/p/6048599.html http://www.cnblogs.com/candy99/p/5968110.html}

f[i]=min{f[j]+s*(p[n]-p[j])+t[i]*(p[i]-p[j])}

: p是费用，t和p都处理前缀和

然后化啊化，得到：

j<k pj<pk t[i]>(f[k]-f[j])/(p[k]-p[j])-s时k更优

slope(x,y)>slope(y,z)时y不最优，下凸壳

p单增，但是t有负数不单调，所以要二分第一个slope(j,j+1)>=a[i]的j

然后还有一个问题，直接算slope会爆掉double的大小，所以手动去分数（是这个原因吧要不然我真不知道为什么WA了）

PS：我谜一般的看着数组中的元素为什么会自动改变然后突然意识到数组大小忘改了.......神秘的溢出竟然修改了前面的数组元素

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1e6+5;
typedef long long ll;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,s;
int q[N],head,tail;
ll t[N],p[N],f[N];
//inline double slope(int j,int k){
//    return (double)(f[k]-f[j])/(double)(p[k]-p[j])-s;
//}
void dp(){
    for(int i=1;i<=n;i++){
        int l=0,r=tail;
//        while(l<r){
//            int mid=(l+r)>>1;
//            if(slope(q[mid],q[mid+1])>=(double)t[i]) r=mid;
//            else l=mid+1;
//        }
        while (l<r){
            long long mid=(l+r)/2;
            if (f[q[mid+1]]-f[q[mid]]>=(s+t[i])*(p[q[mid+1]]-p[q[mid]])) r=mid;
            else l=mid+1;
        }
        int j=q[l];
        f[i]=f[j]+t[i]*(p[i]-p[j])+s*(p[n]-p[j]);
//        while(head<tail&&slope(q[tail-1],q[tail])>slope(q[tail],i)) tail--;
//        q[++tail]=i;
        while(head<tail&&(f[i]-f[q[tail]])*(p[q[tail]]-p[q[tail-1]])<=(f[q[tail]]-f[q[tail-1]])*(p[i]-p[q[tail]])) tail--;
        q[++tail]=i;
    }
    printf("%lld",f[n]);
}
int main(){
    //freopen("in.txt","r",stdin);
    n=read();s=read();
    for(int i=1;i<=n;i++) t[i]=t[i-1]+read(),p[i]=p[i-1]+read();
    dp();
}