李白打酒
話說大詩人李白,一生好飲。幸好他從不開車。
一天,他提着酒壺,從家裡出來,酒壺中有酒2鬥。他邊走邊唱:
無事街上走,提壺去打酒。
逢店加一倍,遇花喝一鬥。
這一路上,他一共遇到店5次,遇到花10次,已知最後一次遇到的是花,他正好把酒喝光了。
請你計算李白遇到店和花的次序,可以把遇店記為a,遇花記為b。則:babaabbabbabbbb 就是合理的次序。像這樣的答案一共有多少呢?請你計算出所有可能方案的個數(包含題目給出的)。
注意:通過浏覽器送出答案。答案是個整數。不要書寫任何多餘的内容。
快速解題思路:dfs
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 15
int ans;
void dfs(int alco,int store,int flower, int pre){
if(store == 0 && flower == 0 ){
if(pre == 0 && alco == 0)ans++;
return ;
}
if(store > 0){
dfs(alco*2,store-1,flower,1);
}
if(alco > 0 && flower > 0){
dfs(alco-1,store,flower-1,0);
}
return ;
}
int main(){
ans = 0;
dfs(2,5,10,-1);
printf("%d\n",ans);
return 0;
}