蓝桥杯-李白打酒加强版

举报
别团等shy哥发育 发表于 2023/04/04 23:02:38 2023/04/04
【摘要】 @toc 1、问题描述话说大诗人李白, 一生好饮。幸好他从不开车。一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱:无事街上走,提显去打酒。 逢店加一倍, 遇花喝一斗。这一路上, 他一共遇到店 N 次, 遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了。请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?注意: 显里没酒 ( 0 斗) 时遇店是合法的, 加倍...

@toc

1、问题描述

话说大诗人李白, 一生好饮。幸好他从不开车。

一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱:

无事街上走,提显去打酒。 逢店加一倍, 遇花喝一斗。

这一路上, 他一共遇到店 N 次, 遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?

注意: 显里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。

输入格式

第一行包含两个整数 NM.

输出格式

输出一个整数表示答案。由于答案可能很大,输出模 1000000007 的结果.

样例输入

5 10

样例输出

14

样例说明

如果我们用 0 代表遇到花,1 代表遇到店,14 种顺序如下:

010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100

评测用例规模与约定

对于 40% 的评测用例: 1≤N,M≤10 。

对于 100% 的评测用例: 1≤N,M≤100 。

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

2、解题思路

直接暴力递归,用count计数,设计一个函数fun(int a,int b,int c),用a表示李白遇见的是店,b表示遇见的是花,c表示酒显中的剩余酒量。

  • 递归出口:(a==0&&b==1&&c==1),店没了,题中要求最后一次遇见的是花,所以b=1,因为遇见花要喝一斗酒,所以c=1

  • 若遇见的是店:fun(a-1,b,c*2);,店-1,酒量加倍。

  • 若遇见的是花:fun(a,b-1,c-1),花-1,酒量-1。

3、代码实现

private static int count=0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        System.out.println(fun(n,m,2));
    }

    public static int fun(int a,int b,int c){
        //出口:最后一次遇到花,说明店没有了,酒剩最后一抖,最后一次赏花后会喝完
        if(a==0&&b==1&&c==1){
            count++;
        }
        if(a>0){//碰到店了  酒量加倍
            fun(a-1,b,c*2);
        }
        //碰到花了,花-1,酒量-1
        if(b>1){
            fun(a,b-1,c-1);
        }
        return count;
    }

image.png

虽然做出来了,但这个只能通过40%的用例,剩下的60%超时了。最优解估计是DP,这个后面再研究吧。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。