任务安排2

题意

\(N\)个任务排成一个序列，分成若干批，执行一批任务所需的时间是启动时间加上每个任务所需时间之和。
同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数\(C_i\)。
求最小的总费用。

思路

设f[i][j]为把前i个任务分成j批的最小费用。
f[i][j]=min{f[k][j-1]+(s*j+sumt[i])*(sumc[i]-sumc[k])}(0<=k<j)
这是O(N^3)的，不能过。
考虑如何降掉一维的复杂度。发现枚举的j是为了记录分了几批，进而记录累计的启动时间，而我们可以将这个启动时间提前累加（费用提前计算）。
具体地，将第二维去掉，f[i]=min{f[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j])}。
即不考虑这一批任务启动时间费用的影响，而是一起提前累加，把后面的费用（当前的也算在里面了）都提前累加（即s*(sumc[n]-sumc[j]))。
这是O(N^3)的，有没有更优秀的算法？
对于f[i]=min{f[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j])}这个式子，我们把min去掉再化开，将只与j有关的放到一边：
f[j]=(sumt[i]+s)*sumc[j]+f[i]-sumt[i]*sumc[i]-s*sumc[n]
可以看出这是形如y=kx+b的东西
(sumc[j],f[j])即为斜率为(sumt[i]+s)的直线上一点。
我们发现f[i]是在右边的b中的，而其它的量都是定值，那么我们最小化b即可最小化f[i]。

那么问题变成了从若干个决策点(sumc[j],f[j])中找出使得这条直线截距最小的一个点即为转折点。
发现只有下凸壳的点才能作为决策点，那么用单调队列维护下凸壳（即斜率单调递增）即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

int n, s;
int sumt[10001], sumc[10001], f[10001], q[10001];

int main() {
	scanf("%d %d", &n, &s);
	for (int i = 1, t, c; i <= n; i++) {
		scanf("%d %d", &t, &c);
		sumt[i] = sumt[i - 1] + t;
		sumc[i] = sumc[i - 1] + c;
	}
	memset(f, 0x3f, sizeof(f));
	f[0] = 0;
	int l = 1, r = 1;
	for (int i = 1; i <= n; i++) {
		while (l < r && (f[q[l + 1]] - f[q[l]]) <= (s + sumt[i]) * (sumc[q[l + 1]] - sumc[q[l]]))
			l++;//k单调递增，需维护凸壳头
		f[i] = f[q[l]] - sumc[q[l]] * (s + sumt[i]) + sumt[i] * sumc[i] + s * sumc[n];
		while (l < r && (f[q[r]] - f[q[r - 1]]) * (sumc[i] - sumc[q[r]]) >= (f[i] - f[q[r]]) * (sumc[q[r]] - sumc[q[r - 1]]))
			r--;//维护下凸壳
		q[++r] = i;
	}
	printf("%d", f[n]);
}

任务安排3

题意

任务安排2中，每个任务的执行时间可能为负数。

思路

这就意味着斜率(sumt[i]+s)并不是单调递增的，那么不能仅仅把队头作为决策点。
那么在下凸壳上二分即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long

int n, s, l, r;
int sumt[300001], sumc[300001], f[300001], q[300001];

int find(int k) {
	if (l == r)
		return q[l];
	int L = l, R = r;
	while (L < R) {
		int mid = L + R >> 1;
		if (f[q[mid + 1]] - f[q[mid]] <= k * (sumc[q[mid + 1]] - sumc[q[mid]]))
			L = mid + 1;
		else
			R = mid;
	}
	return q[L];
}

signed main() {
	scanf("%lld %lld", &n, &s);
	for (int i = 1, t, c; i <= n; i++) {
		scanf("%lld %lld", &t, &c);
		sumt[i] = sumt[i - 1] + t;
		sumc[i] = sumc[i - 1] + c;
	}
	memset(f, 0x3f, sizeof(f));
	f[0] = 0;
	l = 1, r = 1;
	for (int i = 1; i <= n; i++) {
		int p = find(s + sumt[i]);
		f[i] = f[p] - sumc[p] * (s + sumt[i]) + sumt[i] * sumc[i] + s * sumc[n];
		while (l < r && (f[q[r]] - f[q[r - 1]]) * (sumc[i] - sumc[q[r]]) >= (f[i] - f[q[r]]) * (sumc[q[r]] - sumc[q[r - 1]]))
			r--;
		q[++r] = i;
	}
	printf("%lld", f[n]);
}

猫的运输

题意

有\(m\)条猫在n\(座山上，山之间还有不同的距离，\)p\(个饲养员去接它们（一个饲养员从山1走到山n）。 又知猫玩耍到\)Ti\(时刻，如果饲养员在\)t\(时刻到了这座山，那么这条猫的等待时间为\)t-T_i$。
求所有猫最小的等待时间。

思路

先考虑如何列出原始dp方程。
对于每只猫，设Ai=Ti-\(\sum\) Dj(1\(\leq\)j\(\leq\) Hi)，即Ai时刻出发去接猫它的等待时间为0，那么t时刻去接它，等待时间即为t-Ai。
将Ai从小到大排序，可以发现每个饲养员接的肯定是一段连续区间的猫（11112222211111，这一段代表饲养员1，2接猫的位置，可以发现前面的1归给2接会更优）。
那么设f[i][j]为前i个饲养员带走前j个猫的最小等待时间。
f[i][j]=min{f[i-1][k]+(j-k)*t-(sumAj-sumAk)}(0\(\leq\)k\(<\)j)
考虑将第二维进行斜率优化。
将式子拆开，得f[i-1][k]+sumAk=Aj*k+f[i][j]-Aj*j+sumAj
A已经排过序了，我们可以按照“任务安排2”的操作来做这道题。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long

int n, m, p;
int a[100001], d[100001], s[100001], f[101][100001], q[100001], g[100001];

signed main() {
	scanf("%lld %lld %lld", &n, &m, &p);
	for (int i = 2; i <= n; i++)
		scanf("%lld", &d[i]), d[i] += d[i - 1];
	for (int i = 1, h, t; i <= m; i++) {
		scanf("%lld %lld", &h, &t);
		a[i] = t - d[h];
	}
	std::sort(a + 1, a + m + 1);
	for (int i = 1; i <= m; i++)
		s[i] = s[i - 1] + a[i];
	int l, r;
	memset(f, 127, sizeof(f));
	f[0][0] = 0;
	for (int i = 1; i <= p; i++) {
		q[l = r = 1] = 0;
		for (int j = 1; j <= m; j++)
			g[j] = f[i - 1][j] + s[j];
		for (int j = 1; j <= m; j++) {
			while (l < r && a[j] * (q[l + 1] - q[l]) >= g[q[l + 1]] - g[q[l]])
				l++;
			f[i][j] = g[q[l]] + a[j] * (j - q[l]) - s[j];
			while (l < r && (g[j] - g[q[r]]) * (q[r] - q[r - 1]) <= (g[q[r]] - g[q[r - 1]]) * (j - q[r]))
				r--;
			q[++r] = j;
		}
	}
	printf("%lld", f[p][m]);
}

总结

斜率优化是将dp方程化成形如y=kx+b的形式，（例任务安排2中）x,y只j有关，k只与i有关，b中包含着要求的量，
那么每个决策点j都可以表示成一个坐标系上的一个点(x,y)，而每个i都有固定的k。
这一条直线通过不同的决策点会有不同的截距b，这时最（大/小）化截距使得转移进行。