【问题描述】
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：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个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
【数据输出】输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。
【样例输入】
10
2 3 5
2 3 5 6 7
【样例输出】
2
新人求教大神啦 麻烦给出思路和代码～

第一直觉是贪心算法和广度搜索~

还是提示一下吧~这题感觉用递归实现~开一个足够大的数组~里面存放走过该位置所踩的石子总数~用小的覆盖大的~如果遇到大的就进行剪枝~感觉这个更类似深度搜索~上楼的说法还要再更正一下~
fun(……)
{
    ……
    for (i=S;i<=T;++i)
    {
        ……
        if (……)
           fun(……);
    }
}

大体递归框架就是这样……~

没有那么麻烦的。

s[L] = {MAX, MAX, ......}
for (i = 0;i <= L;i++)
{
    s[i] = min(s[i - (S...T)]);
    if (i 有石头) s[i] += 1;
}

可以看到s[i] 至多与 s[i - T] 有关，开个s[T] 的数组就行，不过L最大不过109，没有必要。

[此贴子已经被作者于2017-3-1 16:51编辑过]

想到一种情况，如果青蛙可以转身，会不会对结果有影响，或许这才是题目的考点？

有点懵，一会儿想明白回复。

==========================

刚看到。

青蛙从桥的起点开始，不停的向终点方向跳跃。

不考虑了，有兴趣的同学自己想想

[此贴子已经被作者于2017-3-1 17:14编辑过]

感觉是一个动态优化的题目。并不是每次跳进空白点才是最优的，感觉可以构思出一个某次跳进空白点后，后面次次踩石头的线路，不过我目前还没仔细想。

做出来了~还没有加入数据灵活性~但感觉思路应该是没有问题的~

这水贴还是注释掉算了~

[此贴子已经被作者于2017-3-2 08:24编辑过]

还是让代码多飞一会儿再下结论嘛！
如果石头这样排列：“b[MAX]={0,0,0,1,1,0,1,1,0,1};”，应该踩中的石头数为0，你的代码仍然踩了两坨。

大神加油(^ω^)  这我们大一实训任务题 感觉好难的

改了两三个地方~细节问题~

#include<stdio.h>

#define MAX 10
int a[MAX]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};//初始化位置数组为-1
int b[MAX]={0,0,1,0,1,1,0,0,1,1};//初始化石头--0表示没有--1表示有

typedef struct Node 
{
    int s;//最短距离
    int t;//最大距离
    int l;//路径长度
    int count_save;//通关踩中石头总数
}Node;

Node F={0};

void creat();//初始化数据
void fun(int count,int k);//count--当前踩中石头总数--k当前步数

int main()
{
    creat();

    fun(0,0);

    printf("%d\n",F.count_save);

    return 0;
}

void creat()
{
    F.s=2;
    F.t=3;
    F.l=10;
    F.count_save=MAX;//表示通关之前的状态量
}

void fun(int count,int k)
{
    int i=0;
    int temp=count;

    for (i=F.s;i<=F.t;++i)
    {
        int flag=0;//状态变量
        int tempa=0;
            count=temp;//每一次都要更新当前走过石头的总数
        if (i+k<MAX)
            tempa=a[i+k];

        if (i+k<MAX&&a[i+k]==-1)
            flag=1;//如果是第一次走过该路线~

        if (i+k<MAX&&b[i+k])//如果遇到石头
               a[i+k]=++count;//那就让当前踩中石头总数+1
        if ((i+k<MAX)&&(count<tempa||flag)&&(count<F.count_save))//如果没有通关和下一步踩中石头数较小并且比总通过的最小值要小时~
        {
            a[i+k]=count;//记录此时的石头数据

            fun(count,i+k);//进行递归
        }
        else if (i+k>=MAX&&(count<F.count_save))          F.count_save=count;//记录通关的最小数据
    }
}

[此贴子已经被作者于2017-3-2 18:56编辑过]