「IOI2002」任务安排

题意：$n$ 个任务排成一个序列在一台机器上等待完成(顺序不得改变)，这 $n$ 个任务被分成若干批，每批包含相邻的若干任务。从零时刻开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间为 $t_i$。在每批任务开始前，机器需要启动时间 $s$，而完成这批任务所需的时间是各个任务需要时间的总和(同一批任务将在同一时刻完成)。每个任务的费用是它的完成时刻乘以一个费用系数 $f_i$。请确定一个分组方案，使得总费用最小。

一道斜率优化板子题。

我们首先设 $dp _i$ 为安排前 $i$ 个任务的最小费用。可以很轻松的得到状态转移方程：

$$dp _{i}=\min(dp _{i},dp _{j}+sum _{i}\times(fsum _{i}-fsum _{j})+s\times (fsum _{n}-fsum _{j}))$$

其中 $sum _i$ 为 $t _{i}$ 的前缀和，$fsum _{i}$ 为 $f _{i}$ 的前缀和。在写状态转移方程的过程中会用到一个费用提前的思想，因为算启动时间 $s$ 的费用时需要知道前面已经完成了多少批任务，所以我们用 $s\times (fsum _{n}-fsum _{j})$ 先处理之后的费用，因为这批任务启动了一次机器，那么之后的所有物品的费用都会加上这一段时间的费用。

展开转化移项，可以得到：

$$dp _{j}-s\times fsum _{j}=sum _{i}\times fsum _{j}+dp _{i}-sum _{i}\times fsum _{i}-s\times fsum _{n}$$

我们把 $dp _{j}-s\times fsum _{j}$ 看作 $y _{j}$，将 $fsum _{j}$ 看作 $x _{j}$，可以发现这是一个关于 $j$ 的一次函数，斜率为 $sum _{i}$。

同理，经过类似的推理(详情见玩具装箱解析)，用单调队列维护一下即可。

步骤：

1. 取出最优的点，即每次在队头判断是否 $slope(q _{head},q _{head+1})> sum _{i}$，因为最优点是下凸包中第一个斜率大于 $sum _{i}$ 的点，所以如果小于 $sum _{i}$ 就弹出队头；
2. 按照转移方程更新；
3. 维护斜率单调递增，判断 $i$ 这个点是否可以被加入下凸包，即要使得 $slope(q _{tail-1},q _{tail}) < slope(q _{tail},i)$，所以弹出所有满足 $slope(q _{tail-1},q _{tail}) > slope(q _{tail},i)$ 的队尾；
4. 将 $i$ 入队。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=5010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,s,head,tail,q[maxn];
double sum[maxn],fsum[maxn],dp[maxn];
double x(int i)
{
	return fsum[i];
}
double y(int i)
{
	return dp[i]-s*fsum[i];
}
double slope(int i,int j)
{
	return (y(i)-y(j))/(x(i)-x(j));
}
int main()
{
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		sum[i]=sum[i-1]+a;
		fsum[i]=fsum[i-1]+b;
	}
	head=tail=1;
	for(int i=1;i<=n;i++)
	{
		while(head<tail&&slope(q[head],q[head+1])<sum[i])
			head++;
		dp[i]=dp[q[head]]+sum[i]*(fsum[i]-fsum[q[head]])+s*(fsum[n]-fsum[q[head]]);
		while(head<tail&&slope(i,q[tail])<slope(q[tail],q[tail-1]))
			tail--;
		q[++tail]=i;
	}
	printf("%d",(int)dp[n]);
	return 0;
}