[已解决]求大佬给个思路把 实在想不出来了 5555555

知秋@

跳蛙出行

池塘里有n片荷叶排成一行，有一只青蛙在上面跳跃。但是，这只青蛙是只
不同寻常的青蛙，它每跳一次， 只能从一片荷叶跳到相邻的荷叶上，并且，它在
两片荷叶之间，只能跳跃有限次。青蛙可以从任意荷叶出发。间它最多能跳多少
次。

输入说明
第一行为一个整数n，表示荷叶数。
第二行为n-1个整数，第i个整数表示在第i片与第i+1片荷叶之间，青蛙
最多跳多少次(无论是从左到右，还是从右到左，均包括在内)。

输出说明
一个整数，表示跳蛙最多跳跃的次数。

输入样例
5
2 1 2 1
输出样例
5

提示：提示:从第3片出发,按3->4->3->2->1->2的次序跳跃。

最佳答案

月排行榜 / 总排行榜

风过无痕1989

2020-12-21 14:16:55

先留个程序放这里，再慢慢理解他的题意吧：
青蛙站在第 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

跳转到最佳答案楼层

知秋@

我给大家解释一下题，这个题是没毛病的。我能看懂但是不知道怎么下手。
看他输入样例是
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

       莫名其妙的问题，看不懂逻辑约束条件是什么。什么叫 "它在两片荷叶之间，只能跳跃有限次"。它的数学意义是什么？青蛙的目的和意图又是什么，难道就是为了跳着好玩？

知秋@

jackz007 发表于 2020-12-21 10:42
莫名其妙的问题，看不懂逻辑约束条件是什么。什么叫 "它在两片荷叶之间，只能跳跃有限次"。它的数学意 ...

就是别管他意义了  我现在就想要这个题的思路呀 555555

jackz007

知秋@ 发表于 2020-12-21 10:44
就是别管他意义了  我现在就想要这个题的思路呀 555555

     题目都看不懂，怎么能解呢？

知秋@

jackz007 发表于 2020-12-21 10:45
题目都看不懂，怎么能解呢？

题目我能看懂 就是没事思路 下面给的就是两个荷叶间能够跳跃的次数

Sebass

这好像是DP（dynamic programming）啊。
放一个array，size of n. 遍历整个array，当青蛙向左跳然后向右跳什么时候catch outbounds expection 什么时候停计算跳最多的次数。

Sebass

Sebass 发表于 2020-12-21 10:58
这好像是DP（dynamic programming）啊。
放一个array，size of n. 遍历整个array，当青蛙向左跳然后向右 ...

暴力破解的话需要 O(n^2)

风过无痕1989

既然荷叶是排成一行的，就只有前后，又何来左右？

jackz007

        约束条件不够，不知道青蛙想干什么，比如，有 5 片荷叶，青蛙就喜欢在第 2、3 片之间来回跳着玩行不行，为什么不行？

一世轻尘

艹，看了将近半个小时才看懂了，他喵的和图论似的，我来解释一波，就是有n片荷叶（这个n是你自己输入的）然后，每两片荷叶间能跳跃的次数也是由自己定的，也就是输入的2121分别指12片荷叶间最多跳两次，23片荷叶间最多跳一次....然后写个程序问最多能跳几次，也就是它的输出5。
还有，这题直接穷举就行了吧。

一世轻尘

jackz007 发表于 2020-12-21 12:21
约束条件不够，不知道青蛙想干什么，比如，有 5 片荷叶，青蛙就喜欢在第 2、3 片之间来回跳着玩行 ...

约束条件够了，看我的解释

Cool_Breeze

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间只能跳一次

Cool_Breeze

一世轻尘 发表于 2020-12-21 13:10
4和5间只能跳一次

1,2(跳2次)
3,4(跳1次)
5,6(2)
7,8(1)
这样吗？

风过无痕1989

一世轻尘 发表于 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，第三四片荷叶之间能跳两次，而相邻的二三和四五只能跳一次，所以三四片荷叶之间最多只能跳一次

风过无痕1989

先留个程序放这里，再慢慢理解他的题意吧：
青蛙站在第 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