AcWing 303. 运输小猫
题目传送门
一、题意解读
1、一个饲养员从某个时刻出发，能够接走哪些猫
\(①\) 一个饲养员：是哪个饲养员？共有P个，看来需要遍历就可以找到每个饲养员
\(②\) 某个时刻：哪个时刻？这个出发时刻肯定是一个变化的量，暂时不知道怎么处理，记在心里，一会再想
\(③\) 接走哪些猫：这是和上面两个条件相关的结果
\(④\) 小猫的整体等待时间：上面的①②确定下来后，③也就会确定下来，这个④就会通过计算得到
换句话说：要满足什么条件的猫才能够被该饲养员接走? 显然,只需要到达某只猫所在山的时候，并且这只猫已经玩完了就可以接走猫了。
2、用数学语言进行描述问题
设一个饲养员出发的时间是\(st\)，某只猫(具体是哪一只不重要，重要的是整体的等待时间)在第\(i\)座山上玩，并且要玩\(t_i\)时间，该饲养员能够接走该猫只需要出发时间加上赶路时间大于等于猫玩耍的结束时间即可，即\(st + sd_i >= t_i\)时可以接走猫，否则小猫没有玩完，就不想走，你也接不走。
不好理解的话，也举栗子：小猫要玩\(3\)个小时，饲养员走到这座山需要\(2\)个小时，那么饲养员需要在\(1\)这个时间点出发(也就是饲养员在起点休息\(1\)小时后出发去接)，就正好走到这座山时，小猫正好玩完，可以马上接走，等待时间为\(0\)。当然，饲养员也可以晚一点出发，这样，小猫就需要等一会才能被接走。这个关系需要思考一下，很容易搞反了。
注意：\(sd_i=sum(d_1,d_2,...d_i)\)，因为\(d_i\)是指山与山之间的距离，我们现在要计算总距离，就是从起点到\(i\)的距离，当然是使用前缀和了。
\(sd_i\)和\(t_i\)都是固定的，而饲养员的出发时间是可以变化的，故\(st\)时刻出发，可以接走剩下猫中的\(t_i - sd_i <=st\)的猫。因此需要按照所有猫的玩耍结束时间减去山的距离自小到大排序，方便确定饲养员能够接走哪些猫。
3、动态规划
状态表示：
- 集合 \(f[i][j]\)表示前\(i\)个饲养员接走排好序的前\(j\)只猫的所有方案
- 属性 所有方案的最小等待时间
为什么这么定义？因为我们需要答案，需要在状态定义中包含每一个分步的答案，以及最终的答案
为什么是二维的？因为只使用一维无法描述情况。换句话说：能使用一维不使用二维，有了限制条件，才不得不增加维度。
状态转移：\(f[i][j] = min(f[i-1][k] + a_j*(j-k)-(S_j-S_k))\)
其中\(a_j\)是第\(j\)只猫的玩完时间(\(t_i\))减去山的距离(\(d_i\))。
状态转移方程是怎么来的呢？
举个栗子来模拟：
我们已经对小猫的玩耍时间-距离起点的距离按 从小到大排序 \(a_1,a_2,…,a_m\)
饲养员是 按批接走小猫 的，假设要接走 \(a_3,a_4,a_5\) 三只小猫，由于 \(a_3
整理一下：
\(a_5×3?(a_3+a_4+a_5)\)
由此可知需要对\(a\)进行取一下前缀和，这样才方便计算出某个区间内的元素和。
按上面的栗子来理解：\(j=5,k=2\),抽象出下面的式子：
\(a_j*(j-k)-(a_{k+1} + a_{k+2} + ...+a_j) = a_j*(j-k)-(S_j-S_k)\)，其中\(S\)表示\(a\)数组的前缀和。
\(k\)的取值可以从\(0\)到\(j-1\)，当然\(k\)取到\(j\)也是没问题的，表示第\(i\)个人一只猫都没接到，都被前\(i-1\)个饲养员接走了，但是显然多一个人去接的可以减少猫的等待时间，所以\(f[i-1][j]\)不可能是\(f[i][j]\)的最优解，或者说最多与最优解相等，因此也就不用考虑\(k = j\)的情况了。
设\(k^{'}\)是使得\(f[i][j]\)取得最小值的那个\(k\)，所以：\(f[i][j] = f[i-1][k^{'}] + a[j]*(j-k^{'})-(S[j]-S[k^{'}])\)
4、斜率优化
求\(f[i][j]\)时\(i\)和\(j\)相关的变量都是已知的(通过枚举来尝试嘛，当然是已知的啦)，变形得到\(f[i-1][k^{'}] + S[k^{'}] = a[j] * k^{'} + f[i][j] - a[j]*j + S[j]\)，其中\(a[j],j,S[j]\)都是已知的，将\(f[i-1][k^{'}] + S[k^{'}]\)看作\(y\)，\(k^{'}\)看作\(x\)，就得到了一个一次函数，要使\(f[i][j]\)最小即使得截距最小，就可以使用斜率优化了，
具体斜率优化的推导可以参考，写习惯后就可以直接分析这个式子的性质:
随着\(j\)的增加，新加入点集中的点\((k,f[i-1][k] + s[k])\)也是递增的，并且斜率\(a_j\)也是递增的，因为之前已经对\(a\)数组排序了。所以后面的就可以完全仿照任务安排那题了，维护一个斜率自队头向队尾递增的单调队列。
遍历到\(j\)时，查询使\(f[i][j]\)取得最小值的\(k\)，查询到比当前斜率\(a_j\)小的斜率都出队，查询到第一个大于\(a_j\)的斜率就找到了\(k\)。
出队尾时，也是要保证新加入队尾的斜率要严格的大于之前队尾的斜率，否则就要出队尾。
至于如何求队头队尾的斜率，就相当简单了，\((k,f[i-1][k] + s[k])\)是点坐标的形式，队头的斜率等于\(k\)取\(q[hh]\)以及\(q[hh+1]\)这两点构成的斜率，队尾的斜率等于\(k\)取\(q[tt]\)和\(q[tt-1]\)这两点构成的斜率，（斜率表达式较长，这里就不写了，具体表达式见代码即可）。
二、实现代码
#include
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100005;
typedef long long LL;
int n, m, p, q[N];
LL d[N], t[N], a[N], s[N], f[105][N];
int h;
int main() {
cin >> n >> m >> p;
for (int i = 2; i <= n; i++) cin >> d[i], d[i] += d[i - 1];
for (int i = 1; i <= m; i++) cin >> h >> t[i], a[i] = t[i] - d[h];
sort(a + 1, a + m + 1);
for (int i = 1; i <= m; i++) s[i] = s[i - 1] + a[i];
//初始化
memset(f, 0x3f, sizeof f);
for (int i = 0; i <= p; i++) f[i][0] = 0;
for (int i = 1; i <= p; i++) {
int hh = 0, tt = 0;
for (int j = 1; j <= m; j++) {
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;
}