[ABC374F] Shipping 讲解

zrl123456 · 2024-10-06 15:23:30 · 题解

[ABC374F] Shipping

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

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

• --- 本题的难点是缩小 $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 的和的最小值。