蓝桥杯-李白打酒加强版
蓝桥 加强版
2023-06-13 09:15:38 时间
蓝桥杯-李白打酒加强版
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表示酒显中的剩余酒量。
- 递归出口：
(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;
}虽然做出来了，但这个只能通过40%的用例，剩下的60%超时了。最优解估计是DP，这个后面再研究吧。