每日一题：过河 离散化+dp

题意：

桥长度为$L$ ，分布有$n$ 个石子，青蛙每次可以跳 $[S,T]$ 的距离,问青蛙过桥至少要踩多少个石子。

$(1<=S,T<=10,m<=100,a_i<=10^9, a_i 表示第i个石子的位置)$

solution

这是个很显然的dp题，难点在于他的 $a_i$ 达到了 $10^9$ ，所以我们需要压缩一下。

1. 当 $s==t$ 时，答案就是位置能被 $s$ 整除的石子个数。
2. 当 $s!=t$ 时，我们可以发现：假设当前位置为 $x$ ，那么 $x+s*t$ 之后的所有位置是一定可以被走到的。（可以看做是 $s$ 个 $t$ 步相加或 $t$ 个 $s$ 步相加，然后调整某些步的长度即可。）

然后，石子之间的距离就被压缩了，只要相邻的两个石子距离 $>=st$ 的变成 $st$ 即可。

但是这样一压缩，最后的落点就不能确定了，但是起点是已知的，所以干脆倒过来dp。

状态转移方程：

• i 点有石子：$dp[i] = min(dp[i], dp[i+j]+1)$
• i 点无石子：$dp[i] = min(dp[i], dp[i+j])$

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int l, s, t, n, dis, res, a[N], dp[N], vis[N];
int main() {
  cin >> l >> s >> t >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  if (s == t) {
    for (int i = 1; i <= n; i++) {
      if (a[i] % s == 0) res++;
    }
    cout << res << '\n';
    return 0;
  }
  sort(a + 1, a + n + 1);
  int len = s * t;
  for (int i = 1; i <= n; i++) {
    int d = a[i] - a[i - 1];
    if (d > len) d = len;
    dis += d;
    vis[dis] = 1;
  }
  for (int i = dis; i >= 0; i--) {
    dp[i] = 100;
    for (int j = s; j <= t; j++) {
      dp[i] = min(dp[i], dp[i + j] + vis[i]);
    }
  }
  cout << dp[0] << '\n';
  return 0;
}