[NOIP2005]过河

题目描述

有 \(n\) 个点不能踩， 每次只能走 \(S\) 到 \(T\) 这个范围的距离，问你通过 \(L\) 至少需要走到多少石子。

算法分析

发现 \(L\) 的长度十分的长，显然如果直接按照长度 DP 的话时间复杂度会炸

因为有加值关系，离散化是不可以的。 我们发现\(max\{S,T\}\) 的值非常的小， 那么我们可以直接对 \(lcm(S,T)\) 取模， 进行DP， 这样就可以把空间复杂度降为\(2520\)

在原DP上同时进行取模就能够在 \(O(2520 n)\) 的时间复杂度过这道题

代码

#include <cstdio>
#include <algorithm>

const int maxn = 2520 * 110;
const int maxm = 210;
const int mod = 2520;

int f[maxn], a[maxm], d[maxn], n, L, S, T, M;

int min(const int &x, const int &y) {
    return x > y ? y : x;
}

int main() {
    scanf("%d %d %d %d", &L, &S, &T, &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
    std::sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++ i) d[i] = a[i] - a[i - 1], d[i] %= mod, a[i] = a[i - 1] + d[i], f[a[i]] = 1;
    int l = a[n] + T;
    for (int i = 1; i <= l; ++ i) {
        int mn = n;
        for (int j = S; j <= T && j <= i; ++ j) {
            mn = min(mn, f[i - j]);
        }
        f[i] += mn;
    }
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= T; ++ i)
        ans = min(ans, f[l - i]);
    printf("%d", ans);
}