[SDOI2012]任务安排
时间限制：1000MS 内存限制：131072KB
难度： \(7.1\)
-
题目描述
按顺序给定 \(N\) 个子任务，每个任务用时 \(t_i\) ，费用系数 \(f_i\)。
可以把连续的若干个（或一个）子任务合成为一个大任务，大任务的用时和费用系数分别为其中每个子任务的用时之和与费用系数之和。开始一个大任务之前需要准备时间 \(S\)，一个大任务的费用为他的 完成时刻 \(\times\) 费用系数 ，问按顺序执行完所有的大任务后，最小的费用和为多少。
形式化的，将 \(N\) 个任务划分成若干个块，每一组任务 \(M_i\) 花费代价 \((T+\sum{t_j}+S) \times \sum{f_j}\)，\(j \in M_i\)，\(T\) 为执行到这个任务之前花费的时间，求执行完所有任务的最小代价和。
-
输入格式
第一行一个整数 \(N\) ；
而后 \(N\) 行中，第 \(i\) 行包含一个可能为负的整数 \(t_i\) 和一个非负整数 \(f_i\) 。
-
输出格式
一个整数，表示最小的代价和。
-
样例输入
|
1 2 3 4 5 6 |
5 1 1 3 3 2 4 3 2 3 1 4 |
-
样例输出
|
1 |
153 |
-
样例说明
如果分组方案是 \(\{1,2\}\)、\(\{3\}\)、\(\{4,5\}\)，则完成时间分别为 \(\{5,5,10,14,14\}\)，费用 \(C=\{15,10,30,42,56\}\)，总费用就是 \(153\) 。
-
数据规模与约定
对于 \(20\%\) 的数据，\(1 \leq N \leq 1000\) ；
对于另外 \(40\%\) 的数据， \(1 \leq N \leq 300000\) ；
对于前 \(60\%\) 的数据，\(0 \leq t_i \leq 2^8\) ；
对于后 \(40\%\) 的数据，\(1 \leq N \leq 100000\)，\(-2^8 \leq t_i \leq 2^8\) ；
对于 \(100\%\) 的数据， \(0 \leq S, f_i \leq 2^8\) 。
我也不知道为什么时间可以为负，不要问我。
数据来源于 BZOJ 2726 。
已搬至 YZOJ P4253
设 \(f_i\) 为分割前 \(i\) 个任务的最小费用和。计 \(sumt\) 为用时的前缀和，\(sumf\) 为费用系数的前缀和。
如果不考虑准备时间 \(S\) 的话，可以很轻松的写出转移方程 \(f_i = \min\limits_{j=0}^{i-1}\{f_j+{sumt}_i({sumf}_i-{sumf}_j)\}\) 。
但是要考虑准备时间 \(S\) 的话，由于改变前面任务的时间会影响到后面任务的费用，所以这个 DP 就变成有后效性了。（当然，倒过来 DP 也是一种办法。）
注意到这个影响是可以计算的。如果在 \(j\) 这个点进行分割，那么这个点之后的所有任务的完成时间都要多加上 \(S\) ，即任务 \(k\) （\(k > j\)） 的费用多上 \(S \times f_k\) （\(f\) 表示费用系数） ，总费用就多上了 \(S(sumf_N-sumf_j)\) 。
在 DP 的时候可以把这个影响先加到 \(f_i\) 里面来，因为反正都是要加上去的，加的先后顺序没有关系。所以转移方程就变为 \(f_i = \min\limits_{j=0}^{i-1}\{f_j+{sumt}_i({sumf}_i-{sumf}_j)+S(sumf_N-sumf_j)\}\) 。
这样就得到了一个 \(O(N^2)\) 的 DP 能拿到 \(60pts\) 。
不难发现其实这是一个斜率优化的经典模型。对这个转移方程进行一些处理
\(\begin{align} f_i &= f_j+{sumt}_i({sumf}_i-{sumf}_j)+S(sumf_N-sumf_j) \\ \underbrace{f_i}_{b_i} &= \underbrace{f_j+S(sumf_N-sumf_j)}_{y_j}-\underbrace{sumt_i}_{k_i} \cdot \underbrace{sumf_j}_{x_j}+\underbrace{sumt_i \cdot sumf_i}_{const_i} \end{align}\)
其中 \(x_j\) 是单调的，但是斜率 \(k_i\) 却不是单调的（因为可能出现 \(t\) 为负数，所以 \(sumt\) 不具有单调性）。
\(x_j\) 是单调的，意味着仍然可以按照老办法加入新的点维护下凸壳。但是 \(k_i\) 不是单调的，这就意味着没有办法维护单调队列，使队头元素永远是最小的。
所以最简单的办法就是不要弹出队头。因为维护的下凸壳上所有点的斜率都是单调递增的，所以可以在上面二分斜率，找到比当前斜率大的直线中斜率最小的直线，用它的左端点来贡献答案。
这样就可以有 \(O(NlogN)\) 的复杂度足以通过本题了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> typedef long long LLONG; inline int getnum() { register int sgn=1; register char c=getchar(); (c=='-' ? sgn=-1 : 0); while(!(c>='0' && c<='9')) c=getchar(),(c=='-' ? sgn=-1 : 0); register int a=0; while(c>='0' && c<='9') { a*=10;a+=c-'0'; c=getchar(); } return sgn*a; } int st[305050],sf[305050]; LLONG f[305050]; struct _point { LLONG x,y; LLONG operator * (const _point&o)const { return (x*o.y-y*o.x); } _point operator - (const _point&o)const { return (_point){x-o.x,y-o.y}; } }list[305050]; int front,rear; int main() { register int N=getnum(),S=getnum(); for(register int i=1;i<=N;i++) st[i]=st[i-1]+getnum(),sf[i]=sf[i-1]+getnum(); /*for(register int i=1;i<=N;i++) { f[i]=INT_MAX; for(register int j=0;j<i;j++) { register int ts=f[j]+st[i]*(sf[i]-sf[j])+S*(sf[N]-sf[j]); if(ts<f[i]) f[i]=ts; } }*/ list[rear++]=(_point){sf[0],f[0]+(LLONG)S*(sf[N]-sf[0])}; for(register int i=1;i<=N;i++) { _point ts=(_point){1,st[i]}; register int l=front,r=rear-1,ans=-1; if(l==r) ans=l; else while(l<=r) { register int mid=(l+r)>>1; if((list[mid+1]-list[mid])*ts<=0) r=mid-1,ans=mid; else l=mid+1; } if(ans>=0) f[i]=list[ans].y-(LLONG)st[i]*list[ans].x+(LLONG)st[i]*sf[i]; else f[i]=LLONG_MAX>>2; _point tn=(_point){sf[i],f[i]+(LLONG)S*(sf[N]-sf[i])}; while(front+1<rear && (list[rear-1]-list[rear-2])*(tn-list[rear-1])<=0) rear--; list[rear++]=tn; } printf("%lld\n",f[N]); return 0; } |