信息学奥赛一本通 1609：【例 4】Cats Transport

【题目链接】

ybt 1609：【例 4】Cats Transport
洛谷 CF311B Cats Transport

【题目考点】

1. 动态规划：斜率优化动规

【解题思路】

解法1：设a点的前缀和

输入的 $d$ 序列是从 $d_2$ 到 $d_n$ ，共n-1个数字。人为设 $d_1=0$ 。
设 $d$ 序列的前缀和数组 $s$ ，自然 $s_1=0$ 。
思考：一只猫在玩完后，刚好有个饲养员走到这只猫所在的山，将它接走，那么这名饲养员应该从哪一时刻出发？
设 $a_i$ 表示第 $i$ 只猫在时刻 $t_i$ 被一名饲养员接走，接走它的饲养员的出发时刻。
从第1座山走到第 $h_i$ 座山的距离为 $\sum_{x=2}^{h_i}d_x = s_{h_i}-s_1=s_{h_i}$ 。由于饲养员的速度为1米每单位时间，那么从第1座山走到第 $h_i$ 座山花费的时间为 $s_{h_i}$ ，饲养员在 $t_i$ 时刻到达第 $h_i$ 座山，那么饲养员的出发时间 $a_i = t_i-s_{h_i}$
将所有猫的 $a_i$ 从小到大排序。
如果饲养员在 $a_i+x$ 时刻出发，会在 $t_i+x$ 时刻接到第 $i$ 只猫，此时第 $i$ 只猫等待了 $x$ 个单位的时间。
现在设想一个表示时间的数轴，将每只猫的 $a_i$ 标在数轴上，将这样的点叫做 $a$ 类点。各饲养员的出发时刻标记在数轴上，记为 $b_1,...,b_p$ ，这样的点叫做 $b$ 类点。
设 $b_l$ 和 $b_r$ 是相邻的两个 $b$ 类点，那么所有满足 $b_l< a_i \le b_r$ 的 $a$ 类点对应的猫都会被在 $b_r$ 时刻出发的饲养员接走，第 $i$ 只猫的等待时长为 $b_r-a_i$ 。将猫的等待时间称为代价，因此也可以说 $a_i$ 点贡献的代价为 $b_r-a_i$ 。
在这里插入图片描述
要想使代价和最小， $b$ 点一定选择要在某 $a$ 点上，而不会选择在两个 $a$ 点之间。

如果 $b_l<a_x\le...\le a_y<b_r<a_{y+1}$ ，则 $b_l$ 和 $b_r$ 之间 $a$ 点的代价和为： $\underset{b_l< a_i \le b_r}\sum(b_r-a_i)$
将 $b_r$ 点调整到 $a_y$ ， $b_r$ 减小，代价和 $\underset{b_l< a_i \le b_r}\sum(b_r-a_i)$ 会减小。

$a$ 点序列为 $a_0,a_1, ..., a_m$ ，人为添加一个点 $a_0=0$
设 $b$ 点选择的位置为 $a_{b_1}, a_{b_2},...,a_{b_p}$ ，设 $b_0=0$ 。
最后一个选择的点 $a_{b_p}$ 必然是 $a_m$ ，即 $b_p=m$ 。

如果 $b_p<m$ ，则 $a_m$ 对应的猫不会被饲养员接走。如果 $b p > m$ ，不如 $b p = m$ 代价更小。

可以设 $a$ 序列的前缀和 $s u m A$ ， $sumA_i = \sum_{x=1}^ia_x$
已知 $a_l < a_i \le a_r$ 范围内有 $r - l$ 个 $a$ 点，该范围内 $a$ 点的加和 $\underset{a_l<a_i\le a_r}\sum a_i = sumA_r-sumA_l$ 。
满足 $a_l<a_i\le a_r$ 的 $a$ 点的代价加和为 $\underset{a_l< a_i \le a_r}\sum(a_r-a_i)=(r-l)a_r-(sumA_r-sumA_l)$

状态定义

阶段：前 $j$ 个 $a$ 点中选择 $i$ 个点
前 $j$ 个 $a$ 点对应的猫都应该被接走，因此必须选择最后一个 $a$ 点 $a_j$ 作为 $b$ 点
决策：选择哪个 $a$ 点作为下一个 $b$ 点。
策略：选择点的方案
策略集合：在前 $j$ 个 $a$ 点中选择 $i$ 个点的所有方案
条件：代价最小
统计量：代价

状态定义 $dp_{i,j}$ ：在前 $j$ 个 $a$ 点中选择 $i$ 个点，且一定选择 $a_j$ 点的所有方案中，代价最小的方案的代价。
初始状态：
当 $i\ge j$ 时，可以选择每个 $a$ 点都作为 $b$ 点，代价 $dp_{i,j}$ 为0。所以 $dp_{i,0}=0， 0\le i \le p$ 。
当 $i < j$ 且 $i = 0$ 时，有猫但没有饲养员，是不符合条件的，因此设 $dp_{0,j}=\inf,0<j\le m$

状态转移方程

策略集合：在前 $j$ 个 $a$ 点中选择 $i$ 个点，且选择 $a_j$ 点的所有方案
分割策略集合：由于第 $i$ 个选点一定选择 $a_j$ 点，那么根据第 $i - 1$ 个选择的点分割策略集合。

设选择的第 $i - 1$ 个点为 $a_h$ ，选择 $a$ 点的最小值为 $a_0$ ，也就是没有上一个选点，前 $i - 1$ 个饲养员不接猫。选择的 $a$ 点最大为 $a_{j-1}$ ，所以 $0\le h < j$
要想在 $a_0\sim a_j$ 中选择 $i$ 个点且包括 $a_j$ ，使代价最小。那么首先在 $a_0\sim a_h$ 中选择 $i - 1$ 个点且包括 $a_h$ ，可以获得的最小代价为 $dp_{i-1,h}$ 。
$a_h$ 的下一个选择的点为 $a_j$ ， $a_h<a_x\le a_j$ 中的 $a_x$ 产生代价 $\sum_{x=h+1}^j(a_j-a_x)=(j-h)a_j-(sumA_j-sumA_h)=(j-h)a_j+sumA_h-sumA_j$ 。
对于不同的 $h$ 的取值，求代价的最小值。

因此状态转移方程为： $dp_{i,j}=min\{dp_{i-1,h}+(j-h)a_j+sumA_h-sumA_j\},0\le h < j$

进行斜率优化：
方程中去掉 $min$ ，将与 $h$ 相关的当做变量，与整理方程
$-dp_{i-1,h}-sumA_h=j\cdot a_j-h\cdot a_j-dp_{i,j}-sumA_j$
$dp_{i-1,h}+sumA_h=a_j\cdot h+dp_{i,j}-j\cdot a_j+sumA_j$
设 $y=dp_{i-1,h}+sumA_h$ ， $x = h$ ， $k=a_j$ ， $b=dp_{i,j}-j\cdot a_j+sumA_j$
则该方程就是直线方程 $y = k x + b$ ，决策点为 $h, dp_{i-1,h}+sumA_h)$ ，看直线过哪个决策点时截距 $b$ 最小，就可以求出 $dp_{i,j}$ 。
斜率 $a_j$ 随着 $j$ 的增大而增大，因此可以进行队头出队，取队头即为最优决策点。
斜率优化的具体原理、和代码细节不再赘述，参考模板题：
信息学奥赛一本通 1607：【例 2】任务安排 2 | 洛谷 P10979 任务安排 2

求出的 $p$ 个饲养员接 $m$ 只猫的最小代价 $dp_{p,m}$ 即为最终结果

解法2：最后减 $a$ 点加和

$a$ 点序列为 $a_0,a_1, ..., a_m$ ，人为添加一个点 $a_0=0$
设 $b$ 点选择的位置为 $a_{b_1}, a_{b_2},...,a_{b_p}$ ，设 $b_0=0$ 。
最后一个选择的点 $a_{b_p}$ 必然是 $a_m$ ，即 $b_p=m$ 。
已知 $a_l < a_i \le a_r$ 范围内有 $r - l$ 个 $a$ 点。

满足 $a_{b_0}<a_i\le a_{b_1}$ 的 $a$ 点的代价加和为 $\underset{a_{b_0}< a_i \le a_{b_1}}\sum(a_{b_1}-a_i)=b_1a_{b_1}-\underset{0< a_i \le a_{b_1}}\sum a_i$
满足 $a_{b_1}<a_i\le a_{b_2}$ 的 $a$ 点的代价加和为 $\underset{a_{b_1}< a_i \le a_{b_2}}\sum(a_{b_2}-a_i)=(b_2-b_1)a_{b_2}-\underset{a_{b_1}< a_i \le a_{b_2}}\sum a_i$
…
满足 $a_{b_{p-1}}<a_i\le a_{b_p}$ 的 $a$ 点的代价加和为 $\underset{a_{b_{p-1}}< a_i \le a_{b_p}}\sum(a_{b_p}-a_i)=(b_p-b_{p-1})a_{b_p}-\underset{a_{b_{p-1}}< a_i \le a_{b_p}}\sum a_i$
总代价和为：
$\sum_{i=1}^p(b_i-b_{i-1})a_{b_i}-\sum_{i=1}^{b_p}a_i$
后面 $\sum_{i=1}^{b_p}a_i=\sum_{i=1}^ma_i$ 是定值，记为 $s u m A$ ，在动规过程中不用考虑。
只需要考虑不同选择点的方案中，哪种方案的代价 $\sum_{i=1}^p(b_i-b_{i-1})a_{b_i}$ 是最小的。对于相邻选择的点 $a_{b_{i-1}}$ 和 $a_{b_i}$ ，贡献的代价为 $b_i-b_{i-1})a_{b_i}$ 。

状态定义

状态转移方程

策略集合：在前 $j$ 个 $a$ 点中选择 $i$ 个点，且选择 $a_j$ 点的所有方案
分割策略集合：由于第 $i$ 个选点一定选择 $a_j$ 点，那么根据第 $i - 1$ 个选择的点分割策略集合。

设选择的第 $i - 1$ 个点为 $a_h$ ，选择 $a$ 点的最小值为 $a_0$ ，也就是没有上一个选点，前 $i - 1$ 个饲养员不接猫。选择的 $a$ 点最大为 $a_{j-1}$ ，所以 $0\le h < j$
要想在 $a_0\sim a_j$ 中选择 $i$ 个点且包括 $a_j$ ，使代价最小。那么首先在 $a_0\sim a_h$ 中选择 $i - 1$ 个点且包括 $a_h$ ，可以获得的最小代价为 $dp_{i-1,h}$ 。
$a_h$ 的下一个选择的点为 $a_j$ ， $a_h<a_x\le a_j$ 中的 $a_x$ 产生代价 $j-h)a_j$ 。
对于不同的 $h$ 的取值，求代价的最小值。

因此状态转移方程为： $dp_{i,j}=min\{dp_{i-1,h}+(j-h)a_j\},0\le h < j$

进行斜率优化：
方程中去掉 $min$ ，将与 $h$ 相关的当做变量，与整理方程
$-dp_{i-1,h}=j\cdot a_j-h\cdot a_j-dp_{i,j}$
$dp_{i-1,h}=a_j\cdot h+dp_{i,j}-j\cdot a_j$
设 $y=dp_{i-1,h}$ ， $x = h$ ， $k=a_j$ ， $b=dp_{i,j}-j\cdot a_j$
则该方程就是直线方程 $y = k x + b$ ，决策点为 $h, dp_{i-1,h})$ ，看直线过哪个决策点时截距 $b$ 最小，就可以求出 $dp_{i,j}$ 。
斜率 $a_j$ 随着 $j$ 的增大而增大，因此可以进行队头出队，取队头即为最优决策点。
求出的 $p$ 个饲养员接 $m$ 只猫的最小代价 $dp_{p,m}$ ，再减去所有 $a$ 点的加和 $s u m A$ ，即为最终结果。

【题解代码】

解法1：斜率优化动规一般解法设a点的前缀和

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long LL;
LL n, m, p, d[N], s[N], a[N], dp[105][N], sumA[N];
int q[N], l = 1, r = 0;
LL X(int h)
{return h; 
}
LL Y(int i, int h)
{return dp[i-1][h]+sumA[h];
}
LL K(int j)
{return a[j];
}
bool cmp(LL a1, LL b1, LL a2, LL b2)//a1/b1 <= a2/b2
{return a1*b2 <= a2*b1;
}
int main()
{int t, h;cin >> n >> m >> p;for(int i = 2; i <= n; ++i){cin >> d[i];s[i] = s[i-1]+d[i];//s：d数组的前缀和 }for(int i = 1; i <= m; ++i){cin >> h >> t;a[i] = t-s[h];	}sort(a+1, a+1+m);for(int i = 1; i <= m; ++i)sumA[i] = sumA[i-1]+a[i];//sumA:a数组的前缀和 memset(dp, 0x3f, sizeof(dp));for(int i = 0; i <= p; ++i)dp[i][0] = 0;for(int i = 1; i <= p; ++i)//先求出i-1行再求第i行 {l = 1, r = 0;//清空单调队列 for(int j = 1; j <= m; ++j)//0<=h<j{while(l < r && cmp(Y(i, j-1)-Y(i, q[r]), X(j-1)-X(q[r]), Y(i, q[r])-Y(i, q[r-1]), X(q[r])-X(q[r-1])))r--;q[++r] = j-1;while(l < r && cmp(Y(i, q[l+1])-Y(i, q[l]), X(q[l+1])-X(q[l]), K(j), 1))l++;int h = q[l];dp[i][j] = dp[i-1][h]+(j-h)*a[j]+sumA[h]-sumA[j];}}cout << dp[p][m];return 0;
}

解法2：最后减 $a$ 点加和

#include <bits/stdc++.h>
using namespace std;
#define N 100005
typedef long long LL;
LL n, m, p, d[N], s[N], a[N], dp[105][N], sumA;
int q[N*100], l = 1, r = 0;
LL X(int h)
{return h; 
}
LL Y(int i, int h)
{return dp[i-1][h];
}
LL K(int j)
{return a[j];
}
bool cmp(LL a1, LL b1, LL a2, LL b2)//a1/b1 <= a2/b2
{return a1*b2 <= a2*b1;
}
int main()
{int t, h;cin >> n >> m >> p;for(int i = 2; i <= n; ++i){cin >> d[i];s[i] = s[i-1]+d[i];//s：d数组的前缀和 }for(int i = 1; i <= m; ++i){cin >> h >> t;a[i] = t-s[h];sumA += a[i];}sort(a+1, a+1+m);memset(dp, 0x3f, sizeof(dp));for(int i = 0; i <= p; ++i)dp[i][0] = 0;for(int i = 1; i <= p; ++i)//先求出i-1行再求第i行 {l = 1, r = 0;//清空单调队列 for(int j = 1; j <= m; ++j)//0<=h<j{while(l < r && cmp(Y(i, j-1)-Y(i, q[r]), X(j-1)-X(q[r]), Y(i, q[r])-Y(i, q[r-1]), X(q[r])-X(q[r-1])))r--;q[++r] = j-1;while(l < r && cmp(Y(i, q[l+1])-Y(i, q[l]), X(q[l+1])-X(q[l]), K(j), 1))l++;dp[i][j] = dp[i-1][q[l]]+(j-q[l])*a[j];}}cout << dp[p][m]-sumA;return 0;
}