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

题目大意

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

---

题目分析

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

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

$$f[i]=min\lbrace f[j]+(s+T_i-T_j)\times(F_n-F_j)\rbrace$$

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

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

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

$$f[i]=f[j]+(s+T_i)F_n-(s+T_i)F_j-T_jF_n+T_jF_j$$

移项得到：

$$f[i]-(s+T_i)F_n=f_j+T_jF_j-T_jF_n-(s+T_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[]$与阶段有关。
  因此还是推荐将这些属性放在结构体外面比较好。

---

代码

#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;
}