【每日一题】过河题解

最近作业越来越多了啊, 每天写个每日一题都是奢求

Solution

观察题目数据范围石子的数目很少 $m <= 100$ , 青蛙跳的步幅 $s,t <= 10$
但是总长度 $L$ 却是 $1e9$ 级别的
假如 $L$ 很小的话, 我们很容易考虑 $dp[i]$ 表示第 $i$ 这个位置踩的最小石头数
有转移方程 $dp[i] = dp[i - j] + [i \in {stone} ], s <= j <= t$
图片说明
考虑上图的情况, 在 $L$ 高达 $1e9$ 的时候, 每个石头之间的距离 $len$ 将会很大
但是这个距离 $len$ 有很多是无用的情况
为什么呢? 我们可以通过不断的跳缩短距离, 最后决定是否要踩到石头的仅仅是一小段距离
前面的都能通过不停地往前跳抵消掉
那么最后一小段距离最大有多少呢? 我这里取了 $2520$ , 因为 $2520$ 是 $1$ 到 $10$ 的最小公倍数
我们对石头进行缩点, 相邻的距离过大的先对 $2520$ 取模(因为大于等于 $2520$ 总可以通过弹跳抵消)
缩点后总长度会大幅度减小, 数量级别降到了 $2e5$ , 直接做上面的 $dp$ 即可
注意还要特判 $t == s$ 的情况, 此时只需要统计 $a_i$ 中满足 $a_i \% t == 0$ 的情况就行

Code

/*
  autor: Kurisu
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const long long inf = 1e14;
const int N = 1e5 + 5;
const double eps = 1e-10;
const ll mod = 1e9 + 7;
int a[N];
int dp[5000005];
int vis[5000005];
int dist[5000005];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int L;
  int S, T, n;
  cin >> L >> S >> T >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  sort(a + 1, a + 1 + n);
  a[n + 1] = L;
  if(S == T) { // 特判
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
      if(a[i] % T == 0) {
        cnt++;
      }
    }
    cout << cnt << "\n";
    return 0;
  }
  for(int i = 1; i <= n; i++) {
    dist[i] = (a[i] - a[i - 1]) % 2520; // 缩点
  }
  for(int i = 1; i <= n; i++) { // 缩点
    a[i] = a[i - 1] + dist[i];
    vis[a[i]] = 1; // 此处有石头
  }
  L = a[n];
  //cout << L << "\n";
  memset(dp, 0x3f, sizeof(dp));
  dp[0] = 0;
  for(int i = 1; i <= L + T; i++) {
    for(int j = S; j <= T; j++) {
      if(i - j >= 0)
        dp[i] = min(dp[i], dp[i - j] + vis[i]);
    }
  }
  int ans = 1e9;
  for(int i = L; i <= L + T - 1; i++) {
    ans = min(ans, dp[i]);
  }
  cout << ans << "\n";
  return 0;
}

【每日一题】过河 题解

Solution

Code

【每日一题】过河题解