求大佬给个思路把 实在想不出来了 5555555
跳蛙出行池塘里有n片荷叶排成一行，有一只青蛙在上面跳跃。但是，这只青蛙是只
不同寻常的青蛙，它每跳一次， 只能从一片荷叶跳到相邻的荷叶上，并且，它在
两片荷叶之间，只能跳跃有限次。青蛙可以从任意荷叶出发。间它最多能跳多少
次。
输入说明
第一行为一个整数n，表示荷叶数。
第二行为n-1个整数，第i个整数表示在第i片与第i+1片荷叶之间，青蛙
最多跳多少次(无论是从左到右，还是从右到左，均包括在内)。
输出说明
一个整数，表示跳蛙最多跳跃的次数。
输入样例
5
2 1 2 1
输出样例
5
提示：提示:从第3片出发,按3->4->3->2->1->2的次序跳跃。 我给大家解释一下题，这个题是没毛病的。我能看懂但是不知道怎么下手。
看他输入样例是
5
2 1 2 1
也就是1和2能跳2次，2和3能跳1次，3和4能跳2次，4和5能跳1次
提示给的顺序是3 4 3 2 1 2也就是5次
但是这个只让求最大的 也就是这个次序是不唯一的你只需要求出最大值就可以
比如这个你可以是2 1 2 3 4 3 或者 2 1 2 3 4 5 但是不管怎样求出来的最大值都是5次 所以题是没问题的（是不能从1跳到3的）
求个大佬给个代码参考一下吧 本帖最后由 jackz007 于 2020-12-21 10:44 编辑
莫名其妙的问题，看不懂逻辑约束条件是什么。什么叫 "它在两片荷叶之间，只能跳跃有限次"。它的数学意义是什么？青蛙的目的和意图又是什么，难道就是为了跳着好玩？ jackz007 发表于 2020-12-21 10:42
莫名其妙的问题，看不懂逻辑约束条件是什么。什么叫 "它在两片荷叶之间，只能跳跃有限次"。它的数学意 ...
就是别管他意义了我现在就想要这个题的思路呀 555555 知秋@ 发表于 2020-12-21 10:44
就是别管他意义了我现在就想要这个题的思路呀 555555
题目都看不懂，怎么能解呢？ jackz007 发表于 2020-12-21 10:45
题目都看不懂，怎么能解呢？
题目我能看懂 就是没事思路 下面给的就是两个荷叶间能够跳跃的次数 这好像是DP（dynamic programming）啊。
放一个array，size of n. 遍历整个array，当青蛙向左跳然后向右跳什么时候catch outbounds expection 什么时候停计算跳最多的次数。 Sebass 发表于 2020-12-21 10:58
这好像是DP（dynamic programming）啊。
放一个array，size of n. 遍历整个array，当青蛙向左跳然后向右 ...
暴力破解的话需要 O(n^2) 既然荷叶是排成一行的，就只有前后，又何来左右？ 本帖最后由 jackz007 于 2020-12-21 12:23 编辑
约束条件不够，不知道青蛙想干什么，比如，有 5 片荷叶，青蛙就喜欢在第 2、3 片之间来回跳着玩行不行，为什么不行？ 艹，看了将近半个小时才看懂了，他喵的和图论似的，我来解释一波，就是有n片荷叶（这个n是你自己输入的）然后，每两片荷叶间能跳跃的次数也是由自己定的，也就是输入的2121分别指12片荷叶间最多跳两次，23片荷叶间最多跳一次....然后写个程序问最多能跳几次，也就是它的输出5。
还有，这题直接穷举就行了吧。 jackz007 发表于 2020-12-21 12:21
约束条件不够，不知道青蛙想干什么，比如，有 5 片荷叶，青蛙就喜欢在第 2、3 片之间来回跳着玩行 ...
约束条件够了，看我的解释 2->1->2->3->4->5->4 6次 ？ Cool_Breeze 发表于 2020-12-21 13:07
2->1->2->3->4->5->4 6次 ？
4和5间只能跳一次 一世轻尘 发表于 2020-12-21 13:10
4和5间只能跳一次
1,2(跳2次)
3,4(跳1次)
5,6(2)
7,8(1)
这样吗？ 一世轻尘 发表于 2020-12-21 12:39
约束条件够了，看我的解释
按你的解释，输入荷叶数5
1、2 之间跳 2 次
2、3 之间跳 1 次
3、4 之间跳 2 次
4、5 之间跳 1 次
至少也是 6 次，与他要求的输入荷叶数 5，输出也是 5 不符合 风过无痕1989 发表于 2020-12-21 13:47
按你的解释，输入荷叶数5
1、2 之间跳 2 次
2、3 之间跳 1 次
它只能跳相邻的两片荷叶，中间就断开了，跳不到6次的 Cool_Breeze 发表于 2020-12-21 13:28
1,2(跳2次)
3,4(跳1次)
5,6(2)
你那个6.7.8是什么鬼，就五片荷叶 风过无痕1989 发表于 2020-12-21 13:47
按你的解释，输入荷叶数5
1、2 之间跳 2 次
2、3 之间跳 1 次
你看他给的提示，从三开始的，最后4-5之间的那一次他根本就连不进去，也就是说那个没法跳，可能也有其它的跳法，但一定会有两片荷叶之间有一次没跳 风过无痕1989 发表于 2020-12-21 13:47
按你的解释，输入荷叶数5
1、2 之间跳 2 次
2、3 之间跳 1 次
他输入的是2121，第三四片荷叶之间能跳两次，而相邻的二三和四五只能跳一次，所以三四片荷叶之间最多只能跳一次 先留个程序放这里，再慢慢理解他的题意吧：
青蛙站在第 3 片荷叶上，它可以向第 4 片荷叶上跳 1 次，也可以向第 2 片荷叶上跳 1 次；跳到了第 2 片荷叶上，它可以向第 3 片荷叶上跳 1 次，也可以向第 1 片荷叶上跳 1 次；跳到了第 1 片荷叶上，它只能向第 2 片荷叶跳 1 次
#include<stdio.h>
int main()
{
int m, n, count = 0;
printf("请输入荷叶的片数：");
scanf("%d", &n);
printf("请输入青蛙站在第几片荷叶上：");
scanf("%d", &m);
while(m != 1 && m != n)
{
count += 2; // 在其他的荷叶上可以向2个方向跳
m--;
}
count++; // 在第1片和最后一片荷叶只能跳1次
printf("%d\n", count);
********************************
输入5
输入3
输出5
页:
[1]
2