本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-06 15:23:30

[ABC374F] Shipping

题目考察：离散化，dp。
题目简述：
给你序列 $\{s_n\}$ 和两个正整数 $x,k$，求序列 $\{p_n\},\{t_n\}$ 满足：

• $\forall i\in[1,n],s_{p_i}\le t_{p_i}$。
• $\forall i\in[1,n),t_{p_i}=t_{p_{i+1}}$ 或 $t_{p_i}+x\le t_{p_{i+1}}$。
• $\forall i\in[1,n-k],t_{p_i}\ne t_{p_i+k}$。

使得 $\displaystyle\sum_{i=1}^nt_i-s_i$ 最小，求这个值。
数据范围：

• $1\le k\le n\le 100$。
• $1\le x\le 10^9$。
• $\forall i\in[1,n),s_i\le s_{i+1}$。
• $\forall i\in[1,n],1\le s_i\le 10^{12}$。

本题的难点是缩小 $t$ 的范围。

首先，$p$ 序列的顺序是不影响答案的。

因为 $\displaystyle\sum_{i=1}^nt_i-s_i=\sum_{i=1}^nt_i-\sum_{i=1}^ns_i$，顺序不影响 $s,t$ 的和。

然后我们发现 $t_i$ 只可能是两种值（$1\le pos\le n$）：

• 可能是某一个 $s_{pos}$。
• 可能是某一个 $t_{pos}+x$。

贪心的想，第一种显然是因为若 $t_i$ 不是某一个 $s_{pos}$ 节点，则一定不如是前面的那一个 $s_{pos}$ 节点。
第二种是特例，$t_i$ 不能是前面的那一个 $s_{pos}$。

那么我们将时间节点变成所有的 $s_i+jx$（$1\le i,j\le n$），有效的时间变成了 $\Theta(n^2)$ 个。

我们这样就可以 dp 了，将有效的时间离散化（设为序列 $a$），设 $f_{i,j}$ 表示在第 $i$ 位上，且上一个 $t_{pos}$ 是 $j$ 的 $t$ 的和的最小值。

$j$ 这一维一定要加，要不然你不知道是哪一个时间节点。

$f_{i,j}$ 的转移方程比较难写，我们考虑应用刷表法（我们将从 $f_{i,j}$ 转移到 $f_{pos_i,pos_j}$）。
$\max(a_j+x,s_{pos_i})$ 是 $t_{pos}$ 应该设的值，应该设 $pos_i-i$ 个。这样的话我们就可用 $f_{pos_i,pos_j}=\min(f_{pos_i,pos_j},f_{i,j}+\max(a_j+x,s_{pos_i})\times(pos_i-i))$ 这个式子来转移了。

时间复杂度因为实现细节可能是 $\Theta(n^3k)$ 或 $\Theta(n^3k\log n^2)$。

代码