【每日一题】 过河

题意：

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

solution

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

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

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

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

状态转移方程：

• i 点有石子：
• i 点无石子：

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;
}