隐藏
「SDOI2012」任务安排 - 动态规划+斜率优化+CDQ分治维护凸包 | Bill Yang's Blog
0%

「SDOI2012」任务安排 - 动态规划+斜率优化+CDQ分治维护凸包

题目大意

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


题目分析

这道题有一个可以直接斜率优化的弱化版。
我们先想一想动规转移:
设$f[i]$表示完成前$i$个任务对答案时间的贡献。
为什么这么设置状态?
因为时间是会向后影响的,费用是它的完成时刻乘以一个费用系数Fi,如果直接按照答案设置状态是有后效性的。

但是因为每个任务对答案的影响是独立的,因此我们可以单独将贡献设为状态,这样就没有后效性了。

其中$F[]$与$T[]$均为对题目原数组的前缀和,而后半部分是$F_n-F_j$而不是$F_i-F_j$的原因就是计算的对答案的影响。

这个动规是有点难度的,当然网上也有从后往前动规的方法似乎可以避开这个问题。

然后我们考虑对这个方程进行优化:
展开得到:

移项得到:

根据以前写的斜率优化详解我们可以将$f[i]-(s+T_i)F_n$设为纵坐标$y$,将$(s+T_i)$设为斜率$k$,将$F_j$设为横坐标$x$,将$f[i]-(s+T_i)F_n$设为截距$b$。

货币兑换类似地,要使得截距最小,对于相同斜率的直线,显然在下凸包上取到。

因为斜率不单调所以不能直接使用单调队列求解,又因为插入的点$x$单增,斜率$k$不单调,因此可以使用二分或CDQ分治或平衡树解决。

二分似乎很简单,每一次在凸包上二分斜率找到切线即可。
但是我选择CDQ分治。

具体实现和货币兑换基本一样。


细节

  • $x$和$y$都在long long级别,计算斜率会炸精度,转为交叉相乘。
  • 不要直接将$T[]$、$F[]$放在结构体中,因为第一步按照斜率排序会破坏原有的阶段顺序。
    货币兑换中我们将属性放在结构体中的原因是因为其$a$和$b$是结点本身属性,与阶段无关,但是本题就不一样了,$T[]$与$F[]$与阶段有关。
    因此还是推荐将这些属性放在结构体外面比较好。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=300005;
struct Point {
LL t,f;
int id;
LL k,x,y;
bool operator < (const Point& b) const {
return k<b.k;
}
} p[maxn],tmp[maxn];
int n,s;
LL f[maxn],T[maxn],F[maxn];
bool cmp(const Point& a,const Point& b) {
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double Up(int x,int y) {
return p[y].y-p[x].y;
}
double Down(int x,int y) {
return p[y].x-p[x].x;
}
void CDQBinary(int Left,int Right) {
if(Left==Right) {
p[Left].x=F[Left];
p[Left].y=f[Left]+T[Left]*F[Left]-T[Left]*F[n];
return;
}
int mid=(Left+Right)>>1,lpos=Left,rpos=mid+1;
for(int i=Left; i<=Right; i++)
if(p[i].id<=mid)tmp[lpos++]=p[i];
else tmp[rpos++]=p[i];
for(int i=Left; i<=Right; i++)p[i]=tmp[i];
CDQBinary(Left,mid);
deque<int>Q;
for(int i=Left; i<=mid; i++) { //维护左区间下凸壳
while(Q.size()>=2&&Up(Q[Q.size()-2],Q.back())*Down(Q[Q.size()-2],i)>Down(Q[Q.size()-2],Q.back())*Up(Q[Q.size()-2],i))Q.pop_back();
Q.push_back(i);
}
for(int i=mid+1; i<=Right; i++) {
while(Q.size()>=2&&Up(Q.front(),Q[1])<p[i].k*Down(Q.front(),Q[1]))Q.pop_front();
f[p[i].id]=min(f[p[i].id],p[Q.front()].y-p[i].k*p[Q.front()].x+p[i].k*F[n]);
}
CDQBinary(mid+1,Right);
merge(p+Left,p+mid+1,p+mid+1,p+Right+1,tmp,cmp);
int tot=0;
for(int i=Left; i<=Right; i++)p[i]=tmp[tot++];
}
int main() {
n=Get_Int();
s=Get_Int();
for(int i=1; i<=n; i++) {
T[i]=T[i-1]+Get_Int();
F[i]=F[i-1]+Get_Int();
p[i].k=T[i]+s;
p[i].id=i;
f[i]=1e17;
}
sort(p+1,p+n+1);
CDQBinary(0,n);
printf("%lld\n",f[n]);
return 0;
}
姥爷们赏瓶冰阔落吧~