【每日一题】过河

过河

https://ac.nowcoder.com/acm/problem/16655

题目

题目描述：

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。

在桥上有一些石子，青蛙很讨厌踩在这些石子上。

由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。

坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。

青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。

当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

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

输入描述：
第一行有一个正整数L（1<=L<=10⁹），表示独木桥的长度。
第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1<=S<=T<=10，1<=M<=100。
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。

所有相邻的整数之间用一个空格隔开。

输出描述：
只包括一个整数，表示青蛙过河最少需要踩到的石子数。

解析

这道题：离散化+dp

这道题dp不难，难在离散化_{（我觉得）}。

动态规划：

每次写题第一句：动态规划最重要的就是递推和数组形态。

因为这道题我们要考虑的因素只有该点484石子，所以一维数组就行了。

状态转移方程就是：

dp[i] = min(dp[i], dp[i - j] + visited[i]);
//s <= j <= t，判断该位和前面可以跳到这一位的转移数据的最小值
//visited数组表示当前位是否有石子，有为1，没有为0（表示有石子就要+1计数）

下面的重点就是，离散化：

这是我第一次写离散化的题目。
简单来说就是将一个超长的区间变短，但是要保持效果是一样的。
我们现在用数组模拟一个数轴，数组取值0/1，表示该位置上有没有石头，但是题目大小是1e9，所以我们要离散化压缩。
我们在这里离散化的长度为S * T，也就是说，只要相邻两个点之间的距离大于S * T的话，直接把距离变成S * T。
为什么变成S * T呢？假如要到当前点，在该点前S * T位置之前的点，是一定可以有方法到的。

所以我们的离散化操作就是：

for (int i = 1; i <= m; i++) {
    int dis = stone[i] - stone[i - 1];
    if (dis >= s * t) dis = s * t;
    now[i] = now[i - 1] + dis;
    visited[now[i]] = 1;
}

打代码打代码：

先用一个数组储存下变量和我们原来所以石头的位置。
因为不知道变量是不是有序的，所以我们排个序。
特判一下相等的情况，不相等就离散化。
按照上述方法离散化。
然后按照上述方法递推。
最后再在dp数组在最后一个石头后面找最小值。

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false);
//代码预处理区

const int INF = 0x3f3f3f3f;
const int MAX = 1e6 + 7;
int stone[107], now[107];
int visited[MAX], dp[MAX];
//全局变量区

int main() {
    IOS;
    int l; cin >> l;
    int s, t, m; cin >> s >> t >> m;
    for (int i = 1; i <= m; i++) cin >> stone[i];
    sort(stone + 1, stone + 1 + m);
    if (s == t) {
        int cnt = 0;
        for (int i = 1; i <= m; ++i)
            if (stone[i] % s == 0)cnt++;
        cout << cnt << endl;
        return 0;
    }
    now[0] = 0;
    memset(visited, 0, sizeof visited);
    for (int i = 1; i <= m; i++) {
        int dis = stone[i] - stone[i - 1];
        if (dis >= s * t) dis = s * t;
        now[i] = now[i - 1] + dis;
        visited[now[i]] = 1;
    }
    l = now[m] + s * t;
    memset(dp, INF, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= l; i++)
        for (int j = s; j <= t; j++)
            if (i >= j) dp[i] = min(dp[i], dp[i - j] + visited[i]);
    int ans = INF;
    for (int i = now[m]; i <= l; i++)
        ans = min(ans, dp[i]);
    cout << ans << endl;
    return 0;
}
//函数区

每日一题文章被收录于专栏

憨憨的专栏