题目描述

链接：https://ac.nowcoder.com/acm/problem/16655
来源：牛客网

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

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

输入描述

第一行有一个正整数L（1<=L<=109），表示独木桥的长度。
第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1<=S<=T<=10，1<=M<=100。
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。
所有相邻的整数之间用一个空格隔开。

输出描述

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

题目思路

状态转移方程：dp[i] = min(dp[i-j] + is[i]) (s<=j<=t) (is[i] == 1, 说明i位置有石头；is[i] == 0，没有）。

怎样进行离散化

由于 l 最大可达到1e9, 一定不能直接开1e9的数组来，同时循环次数也应该想办法降低。

可以发现，在 l 中，有很多位置是空的，因此可以利用取模的方式缩短距离。由于1~10的最小公倍数是2520，所以可以对2520取模。这样dp数组的大小就降到了10^5，实现了离散化存储（即利用一个新的位置代替原位置存储）。

for(int i=1; i<=m; i++)
    {
        dis[i] = (sto[i]-sto[i-1])%MOD;//计算石子间距离
    }
for(int i=1;i<=m;i++)
    {
        sto[i] = sto[i-1] + dis[i];//将离散处理后的石子位置放回sto数组
        is[sto[i]] = 1;//桶排序的思想，标识出哪个位置有石子
    }

离散化结束后，可以直接将最后一个石子的位置作为结束位置。

l = sto[m];

dp数组的填充

由于在利用状态转移方程循环填充dp数组的过程中，s以前的位置是顾及不到的，所以要提前进行初始化。

//这一部分位置是不可能跳到的，所以直接置最大值
for(int i=1;i<s;i++)
        dp[i] = 305;
//这一部分位置是第一步可能跳到的
for(int i=s;i<=t;i++)
    {
        if(is[i]) dp[i] = 1;
    }

初始化结束后对dp数组进行进一步填充：

for(int i=t+1;i<l+t;i++)
    {
        dp[i] = 305;
        for(int j=s;j<=t;j++)
        {
            dp[i] = min(dp[i-j]+is[i], dp[i]);    
        }
    }

找最小值

到达终点有两种情况，恰好到达终点，或超过终点。因此要对dp[l]~dp[l+t]（左闭右开）进行遍历，找最小值。

int minx = 1e9;
for(int i=l;i<l+t;i++)
    {
        minx = min(minx,dp[i]);
    }

完整代码

#include<bits/stdc++.h>
using namespace std;
const long long MAXN = 5e6+5;
const int MOD = 2520;//1~10的最小公倍数 
int dp[MAXN] = {0};
long long sto[105];
int dis[105], is[MAXN]={0};
int main()
{
    int l, s, t, m;
    scanf("%d%d%d%d", &l, &s, &t, &m);
    int i=1;
    while(i<=m)
    {
        scanf("%lld",&sto[i]);
        i++;
    }
    sort(sto+1,sto+1+m);
    sto[m+1] = l;
    for(int i=1; i<=m; i++)
    {
        dis[i] = (sto[i]-sto[i-1])%MOD;
    }
    for(int i=1;i<=m;i++)
    {
        sto[i] = sto[i-1] + dis[i];
        is[sto[i]] = 1;
    }
    l = sto[m];
    for(int i=1;i<s;i++)
        dp[i] = 305;
    for(int i=s;i<=t;i++)
    {
        if(is[i]) dp[i] = 1;
    }
    for(int i=t+1;i<l+t;i++)
    {
        dp[i] = 305;
        for(int j=s;j<=t;j++)
        {
            dp[i] = min(dp[i-j]+is[i], dp[i]);    
        }
    }
    int minx = 1e9;
    for(int i=l;i<l+t;i++)
    {
        minx = min(minx,dp[i]);
    }
    printf("%d\n", minx);
    return 0;
}

总结

看了好多题解才把这道题勉强做出来，大家都说这道题目的动规方程一目了然，可是我仅仅在这里就卡了很久。。

为什么只要每一步都选取可选取的最小值，最终就可以达到整条路径的最小值呢？对于贪心和动态规划的区别我还是不太能分得清楚。

最重要的是，学到了一种数组离散化的方法，虽然卡了很久，但还是值得哒。

过河——动态规划，离散化