AcWing 303. 运输小猫
\(AcWing\) \(303\). 运输小猫
一、题目描述
有 \(n\) 座 山 和 \(m\) 只 喵酱，\(P\) 位 饲养员
第 \(i\) 座 山 和第 \(i−1\) 座 山 相隔 \(D_i\) 的距离
第 \(i\) 只 喵酱 会在第 \(H_i\) 座 山 上玩耍，直到 \(T_i\) 时刻 停止，并等待 饲养员 来接他
所有的 饲养员 初始 都在第 \(1\) 座山上，现安排这些 饲养员 的 出发时刻（可以是 负数）
饲养员 以 单位时间内行走\(1\)个单位长度 的速度沿 坐标轴 出发，接走经过的 山 上所有 等待中 的 喵酱
喵酱们 很心急，求一种 饲养员 的 出发方案，使得所有 喵酱 的 等待时间之和最少
二、分析
首先用 前缀和 \(sd_i\) 表示第 \(i\) 座 山 到 起点 第 \(1\) 座 山 的 距离
对于每只 喵酱 一经等待就恰好被接走 的 饲养员 出发时间 为：\(t_i−sd_{h_i}\) （饲养员到达时刚好接走）
令 \(a_i=t_i−sd_{h_i}\) 表示第 \(i\) 只 喵酱 的 最早接走的出发时刻
那么对于第 \(st\) 时刻 出发 的 饲养员，他能接走的 喵酱 满足：\(a_i≤st\)
如果我们按\(a_i\)进行 由小到大 排序,那么 某个 饲养员 就可能连续接走一组小猫，按我的理解就是：原来是杂乱无序的，不方便处理计算，如果我们梳理清楚了业务关系，把 因变量 由小到大进行排序，就方便利用各种算法、模型了，这样看来，梳理清楚关系，然后由小到大排序就是非常必要的动作了。
闫氏\(DP\)分析法
状态表示—集合 \(f_{i,j}\)：已经派出 \(i\) 名 饲养员，且接走了前 \(j\) 只 喵酱 的方案
状态表示—属性 \(f_{i,j}\)：方案中，每个 喵酱 的 等待时间之和 最小 \(Min\)
状态计算：
考虑 \(i−1\) 阶段接走 \(k(0≤k<j)\) 只 喵酱，为了让 \(k+1∼j\) 的 喵酱 等待时间之和最少
可以列出如下式子：设第 \(i\) 名 饲养员 的 出发时间 为 \(T\)
根据 贪心的思想，应让第 \(i\) 名 饲养员 的 出发时间 为 \(a_j\)
证明
- 如果\(T<a_j\),那么\(i\)号饲养员到达时，\(j\)喵酱没有玩完，不让接。结论：\(T\)太小
- 如果\(T>a_j\),那么\(i\)号饲养员到达时，\(j\)喵酱已经等了一会了，这样就不如早点出发，\(j\)喵酱玩完就接走，节约时间。结论：\(T\)太大
- 如果\(T==a_j\),那么\(i\)号饲养员到达时，\(j\)喵酱刚好玩完，接上就走，节约时间，结论\(T\)正好
对于第 \(i\) 名 饲养员（机器） 带走连续一段的 \(k+1∼j\) 只 喵酱（任务），就是 任务安排 裸题了
于是有如下 转移方程：
- \(s\)为\(a\)数组的预处理前缀和
注：当讨论到\(i\)号饲养员，\(j\)号喵酱时，它两相关的都是常量,\(k\)相关的是变量
出现 \(j×k\) 的项，考虑 斜率优化：令
接下来就是 模板 里经典的：维护 下凸壳的点集，求 第一个 出现在 直线 上的 点
由于本题中的直线斜率 \(a_j\) 我们事先进行了 排序，故他是 单调递增 的
我们就可以同 任务安排2 中一样用 单调队列 在 队头 维护 大于 \(k\) 的 最小斜率
直接套 斜率优化\(DP\) 的模板即可，不需要任何 二分/平衡树/CDQ优化
Code
时间复杂度： \(O(PM)\)
空间复杂度： \(O(PM)\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
const int P = 110;
int n, m;
int p;
int q[N];
ll d[N], t[N];
ll a[N], s[N];
ll f[P][N];
int h;
int main() {
cin >> n >> m >> p;
for (int i = 2; i <= n; i++) cin >> d[i], d[i] += d[i - 1]; //从2开始
for (int i = 1; i <= m; i++) cin >> h >> t[i], a[i] = t[i] - d[h], s[i] = s[i - 1] + a[i];
sort(a + 1, a + m + 1); //由小到大排序,m个喵酱
// dp初始
memset(f, 0x3f, sizeof f);
for (int i = 0; i <= p; i++) f[i][0] = 0; //出动i个饲养员，接0只喵酱，等待0
for (int i = 1; i <= p; i++) { //饲养员，双层循环，小的在外，大的在内
int hh = 0, tt = 0; //哨兵
for (int j = 1; j <= m; j++) { //遍历喵酱
//凸包的斜率单调上升，并且，直线的斜率也是单调上升
//准备在下凸壳中找到第一个斜率大于k的直线，小于k的全部剔除
while (hh < tt &&
(f[i - 1][q[hh + 1]] + s[q[hh + 1]] - f[i - 1][q[hh]] - s[q[hh]]) <= a[j] * (q[hh + 1] - q[hh]))
hh++;
//推出的公式
f[i][j] = f[i - 1][q[hh]] + a[j] * (j - q[hh]) - (s[j] - s[q[hh]]);
//维护下凸壳
while (hh < tt && (f[i - 1][j] + s[j] - f[i - 1][q[tt]] - s[q[tt]]) * (q[tt] - q[tt - 1]) <=
(f[i - 1][q[tt]] + s[q[tt]] - f[i - 1][q[tt - 1]] - s[q[tt - 1]]) * (j - q[tt]))
tt--;
//加入
q[++tt] = j;
}
}
printf("%lld\n", f[p][m]);
return 0;
}
还可以用滚动数组优化
空间复杂度： \(O(M)\)