2020-2021:teams:legal_string:jxm2001:动态规划_2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:动态规划_2 [2020/10/31 22:57]
jxm2001 [习题一]
+++ 2020-2021:teams:legal_string:jxm2001:动态规划_2 [2021/02/11 18:58] (当前版本)
jxm2001 [习题一]
@@ 行 230: / 行 230: @@
 $$
-\text{dp}_i=\max(dp_j+(s_i+i-s_j-j-L-1)^2)
+\text{dp}_i=\min(dp_j+(s_i+i-s_j-j-L-1)^2)
 $$
@@ 行 329: / 行 329: @@
 </code>
 </hidden>
+==== 习题三 ====
+[[https://www.luogu.com.cn/problem/CF311B|CF311B]]
+=== 题意 ===
+给定一条链，链上有 $n$ 个点，编号相邻两点距离为 $D_i$。接下来给定 $m$ 只猫，每只猫位于 $H_i$ 号点，且在第 $T_i$ 秒开始等待。
+接下来有 $p$ 个人，每个人速度为 $1$ 且可以从任意时刻出发且从 $1$ 号点不停止地走到 $n$ 号点并带走所有已经开始等待的猫。
+问所有猫等待时间的最小可能值。
+=== 题解 ===
+对每条猫，计算出使得它等待时间为 $0$ 的出发时间 $t_i$，将 $t_i$ 从小到大排序。
+将序列 $t$ 划分为 $p$ 个区间，每个区间派一个人，显然这个人必须在该区间 $t$ 的最大值的时刻出发。
+设 $\text{dp}(i,j)$ 表示派 $i$ 个人接前 $j$ 只猫需要花费的最小时间，$s_n=\sum t_i$，于是有状态转移方程
+$$
+\text{dp}(i,j)=\min_{k\lt j}\left(\text{dp(i-1,k)}+\sum_{x=k+1}^j (t_j-t_x)\right)=\min_{k\lt j}\left(\text{dp(i-1,k)}+(j-k)t_j+s_j-s_k\right)=\min_{k\lt j}\left(\text{dp(i-1,k)}-s_k-t_jk\right)+jt_j+s_j
+$$
+时间复杂度 $O(mp)$。

2020-2021/teams/legal_string/jxm2001/动态规划_2.1604156261.txt.gz · 最后更改: 2020/10/31 22:57 由 jxm2001