dp 29 过河

题目描述

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

数据范围：

思路分析

此题如果直接进行枚举，

也就是定义dp[ i ] 为 到达第i个点必须经过的最小石子数。然后再从1 开始进行枚举到L。那么就是10^9 * 10 = 10^10.会超时。

这个时候就需要去观察原问题，寻求降低问题复杂度的方法。

注意到M的点数最多只有100个。

那么任意两个M之间，之间的距离可能达到10^7。

我们是没有必要去对这中间的所有情况都进行枚举的。

考虑如下情况。

两个石子之间距离dis,如果距离小于了一次可跳跃的最长距离T，那么此时不能省略这部分距离。

因为可能从前一个石头前面或者后面跳到当前的位置。如果省略了会导致取不到最优解。

当两个石子之间的距离大于1次可跳跃的最长距离T，即如下情况，假设第一个点在0的位置，第二个点在j的位置

0...s...t...j。 t <= j < 2t。对于所有能到j的点，即 j - [s,t] = [j-t, j-s]

0 <= j - t < t, t-s<= j-s < 2t-s。

而中间的这些点位并不存在 石子。不会影响最后的结果。

如此递推，2,3,4,5...n 都不会影响。因此可以直接mod T。

但是modT后需要再加上T，因为如果 j = n*t.。那么mod T后的结果就是0.会和上一个石子冲突。

dp，idx数组开到2000就够了。10*1000 再算上最后的t

上述思路实现的代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[2005];
int idx[2006];
int stone[105];
#define inf 0x7f7f7f7f

int main() {
    int L;
    int S, T, M;
    scanf("%d", &L);
    scanf("%d%d%d", &S, &T, &M);
    for (int i = 1; i <= M; i++) {
        scanf("%d", &stone[i]);
    }

    // 去除到无意义的点位
    sort(stone + 1, stone + 1 + M);
    stone[++M] = L;// 计算最后一个点
    int l = 0;//判断石头压缩后的点位
    for (int i = 1; i <= M; i++) {
        int dis = stone[i] - stone[i - 1];
        if (dis > T) {
            l += dis % T + T;
        } else {
            l += dis;
        }
        idx[l] = 1;
    }


    // 枚举dp[i] 到底第i点必须跳过的最少石子数
    int Length = l + T;// 因为可以从 [S,T] 的范围跳 还能跳过去 所以得把跳过去的也算上

    memset(dp, inf, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i < Length; i++) {
        for (int j = S; j <= T; j++) {
            if (i >= j)
                dp[i] = min(dp[i], dp[i - j] + idx[i - j]);
        }
    }

    // 在成功跳过去的点位里面找最小的那个
    int result = 1e9;
    for (int i = l; i < Length; i++) {
        result = min(result, dp[i]);
    }
    printf("%d\n", result);
    return 0;
}