P15640 [ICPC 2022 Tehran R] Simplification

Amin 会时不时地记录他的股票价格，作为一个数据点 $(t_{i}, p_{i})$ 记在笔记本上，其中 $p_{i}$ 是股票在第 $t_{i}$ 天的价格。这些数据点构成的序列代表了一个**分段线性函数** $F$，展示了一段时间内的价格历史。实际上，$F$ 通过直线段连接每一对连续的点。如果某一天 $t$ 没有记录价格，则可以用 $F(t)$ 作为估计值。 由于他长期跟踪股票价格，收集的数据变得越来越大。因此，他决定通过丢弃一些已记录的数据点来缩减数据，并用剩余的点构造一个新的分段线性函数 $F'$。$F'$ 被称为 $F$ 的一个 **“简化”**。Amin 希望以这样一种方式创建简化，使得 $F'$ 是 $F$ 的一个良好近似。为此，他定义了一个误差度量如下。 设 $F$ 定义在一个严格递增的天数序列 $L = \langle t_{1}, \ldots, t_{n} \rangle$ 上，而 $F'$ 定义在 $L$ 的一个子序列 $L' = \langle t'_{1}, \ldots, t'_{m} \rangle$ 上，其中 $t'_{1} = t_{1}$，$t'_{m} = t_{n}$，并且对于 $1 \leq i \leq m$ 有 $F'(t'_{i}) = F(t'_{i})$。（我们称 $m$ 为 $F'$ 的**大小**。）$F'$ 的**误差**定义为所有 $1 \leq k \leq n$ 中 $|F'(t_{k}) - F(t_{k})|$ 的最大值。例如，在下图中，我们有 $6$ 个数据点，标记为 $1$ 到 $6$，其坐标与第二个样例输入中给出的相同，而 $F'$ 是一个大小为 $3$ 的简化，包含数据点 $1$、$4$ 和 $6$。在此图中，$F$ 用实线描绘，$F'$ 用虚线描绘。$F'$ 的误差度量由点 $2$ 到 $F'$ 的垂直距离体现。 :::align{center}  ::: Amin 的目标是在 $F'$ 的误差不超过给定值 $\delta$ 的前提下，最小化 $F'$ 的大小。

输入的第一行包含一个正整数 $n$（$2 \leqslant n \leqslant 2000$），表示 $F$ 的大小。接下来的 $n$ 行，每行包含两个整数 $t_{i}$, $p_{i}$（$1 \leqslant t_{i}, p_{i} \leqslant 10^{6}$），其中 $p_{i}$ 是股票在第 $t_{i}$ 天的价格。最后一行包含误差限制 $\delta$，它是一个不超过 $10^{6}$ 的非负整数。

在输出中，打印 $F'$ 的最小可能大小。

翻译由 DeepSeek V3.2 完成