计算机科学论坛--求助^^^^^^(那位高手给个标准答案吧,万分感谢!)

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

过河
(river.pas/c/cpp)

【问题描述】

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

【输入文件】

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

【输出文件】

输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。

【样例输入】

10
2 3 5
2 3 5 6 7

【样例输出】

【数据规模】

对于30%的数据，L <= 10000；

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

[问题分析]

此题初看是一个典型的搜索题。从河的一侧到河的另一侧，要找最少踩到的石头数。但从数据范围来看。1..109长度的桥。就算是O(n)的算法也不能在一秒内出解。

如果搜索石子，方法更困难。这要考虑到前面以及后面连续的石子。若换一种方法。用动态规划，以石子分阶段的一维动规，时间复杂度是O(n2)。最多也只有100×100的时间。但是这样分状态就十分复杂。因为石头的分布是没有任何规律，而且会有后效性。

这样只好有回到搜索。搜索石子会和动规一样没有规律。我们一桥的长度为对象进行搜索，然后再加上一个巧妙的剪枝就可以在很短的时间内出解。可以号称为O(m2)。[批注：号称一词已成为湖南OI本世纪流行词汇 ]

[题目实现]

先以时间为对象进行搜索。时间复杂度为O(L)。从桥的一侧到另一侧，中间最多只有100个石子。假设桥长为最大值(109)，石头数也为最大值(100)。这样中间一定会有很多“空长条” (两个石子中的空地)，处理时把这些跳过，就只会有M次运算。关键是找出每一个可以跳过的“空长条”。

我们可以先把青蛙可以跳出的所有可能求出，然后就可以求出可以忽略的“空长条”。

[特殊算法]

a[i]:前i个坐标中石子最小个数,初始为第i个坐标的石子个数

b[i]:第i个石子坐标

动规

a[0]=0;

对n>=t

a[n]=min{a[n]+a[n-s],a[n]+a[n-s-1], ...,a[n]+a[n-t]}

对s=<n<t

a[n]=max{a[n]+a[n-s],a[n]+a[n-s-1],...,a[n]+a[0]}

但由于n较大直接动规会超时。所以要将n压缩

查看坐标，可以发现，如果b[i]-b[i-1]>t，显然对于b[i-1]+t<n<b[i]，a[n]总是等于a[b[i-1]]..a[b[i-1]+t]中的数，因此可对其进行压缩。

注意，在计算过程中，由于其中有一些坐标是永远走不到的，因此需要用一个布尔型的数组c[n]进行判断。方法是，对于c[n],如果0<n<s,则c[n]为false，如果n>s,c[n-t],c[n-t+1],...,c[n-s]都为false,则c[n]也为false。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我总结这个问题是一句话：如果有连续十个石头就必然踩着一次。
M是M个石子在数轴上的位置序列，M1是这M个石子在数轴上的最小位置，M2是这M个石子在数轴上的最大位置。n是踩着石头数。
算法：
n=0;
X=M1;
while(X<M2){
   for(int i=1;i<10;i++){
       X = X+i;
      if(X.indexof(M)){
        flag=true;
      }
        else {
        flag = false;
        break;
      }
   }
      if(flag) n++;
}
reutrn n;

这个可能不一定正确，欢迎大家讨论

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

“三楼的高手”的基本思路是对的，但其中的关于M1和M2的确定可能会有“动态规划”算法，所以这道题困难就在这个地方，否则程序本身无法确定青蛙究竟跳过了多少个石子……

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

而“动态规划”就可以比较好的解决青蛙跳过的石子数据的多少的问题，可惜，我对“动态规划”理解不是很深的……

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

关注ing

是有点难,有空时好好研究一下.


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	78.125ms