光谷企业网站建设,python教程,手机端网站开发流程,建立什么本地网站赚钱蓝桥杯-李白打酒加强版1、问题描述2、解题思路3、代码实现1、问题描述
话说大诗人李白, 一生好饮。幸好他从不开车。
一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱: 无事街上走#xff0c;提显去打酒。 逢店加一倍, 遇花喝一斗。 这一路上, 他一共遇到店 N 次…
蓝桥杯-李白打酒加强版1、问题描述2、解题思路3、代码实现1、问题描述
话说大诗人李白, 一生好饮。幸好他从不开车。
一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱: 无事街上走提显去打酒。 逢店加一倍, 遇花喝一斗。 这一路上, 他一共遇到店 N 次, 遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?
注意: 显里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。
输入格式
第一行包含两个整数 N 和 M.
输出格式
输出一个整数表示答案。由于答案可能很大输出模 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表示酒显中的剩余酒量。 递归出口(a0b1c1),店没了题中要求最后一次遇见的是花所以b1因为遇见花要喝一斗酒所以c1 若遇见的是店: fun(a-1,b,c*2);,店-1酒量加倍。 若遇见的是花fun(a,b-1,c-1),花-1酒量-1。
3、代码实现
private static int count0;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(a0b1c1){count;}if(a0){//碰到店了 酒量加倍fun(a-1,b,c*2);}//碰到花了花-1酒量-1if(b1){fun(a,b-1,c-1);}return count;}虽然做出来了但这个只能通过40%的用例剩下的60%超时了。最优解估计是DP这个后面再研究吧。
