- The 2022 ICPC Asia Tehran Regional Contest
题目描述
Amin 经常在笔记本上记录股票价格，数据点记为 \((t_i, p_i)\)，其中 \(p_i\) 是第 \(t_i\) 天的价格。这些数据点序列构成了一个分段线性函数 \(F\)（即折线图），展示了价格的历史变化。\(F\) 通过直线段连接每一对相邻的点。如果某一天 \(t\) 没有记录价格，则可以用 \(F(t)\) 作为估计值。
随着记录的数据越来越多，Amin 决定通过丢弃一些数据点来减少数据量，并用剩下的点构建一个新的分段线性函数 \(F'\)。\(F'\) 被称为 \(F\) 的“简化版”。
Amin 希望 \(F'\) 能很好地近似 \(F\)。为此，他定义了一个误差度量方式：
-
设 \(F\) 定义在严格递增的时间序列 \(L = \langle t_1, \dots, t_n \rangle\) 上。
-
\(F'\) 定义在 \(L\) 的子序列 \(L' = \langle t'_1, \dots, t'_m \rangle\) 上，其中 \(t'_1 = t_1\) 且 \(t'_m = t_n\)（即必须保留起点和终点）。
-
对于 \(F'\) 中的点，其价格保持不变，即 \(F'(t'_i) = F(t'_i)\)。
-
误差定义为：对于所有原始点 \(1 \le k \le n\)，在 \(t_k\) 时刻 \(F'\) 与 \(F\) 之间的最大垂直距离，即 \(\max |F'(t_k) - F(t_k)|\)。
目标：给定一个误差容限 \(\delta\)，求满足误差不超过 \(\delta\) 的情况下，\(F'\) 的最小尺寸 \(m\)（即最少保留多少个点）。
N只有2000，可以考虑dp
设dp[i]为前i个点选最少的点
思考如何转移，发现两个点之间存在一种连和不连的关系
假设 \(j<i\) 且 j 与 i 之间满足限制，可以连边，那么转移方程为 $ dp[i]=min(dp[i],dp[j]+1) $
考虑如何满足条件，我们对 $ (X_j+E,Y_j)$ $ (X_j-E,Y_j)$ \((X_j,Y_j)\) 和i连边，斜率分别为\(K_a,K_b,K_c\) 如果满足
\(K_b<K_c<K_a\) 则可以满足这个限制，在不断减小集合，如果集合空了，就直接break
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define se second
int n,dp[2005],E;
pair<int ,int >p[2005];
void solve() {cin >> n;for (int i = 1; i <= n; i++) {cin >> p[i].fr >> p[i].se;}cin >> E;memset(dp, 0x3f, sizeof(dp));dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = i;double L = -1e18, R = 1e18;for (int j = i - 1; j >= 1; j--) {double k = 1.0 * (p[j].se - p[i].se) / (p[j].fr - p[i].fr);if (L <= k && k <= R) {dp[i] = min(dp[i], dp[j] + 1);}double kl = 1.0 * (p[j].se + E - p[i].se) / (p[j].fr - p[i].fr);double kr = 1.0 * (p[j].se - E - p[i].se) / (p[j].fr - p[i].fr);L = max(L, kl);R = min(R, kr);if (L > R) break;}}cout << dp[n] << endl;
}
int main() {solve();return 0;
}