蓝桥杯 算法练习 李白打酒

题目：李白打酒

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

一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：

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

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

请你计算李白遇到店和花的次序，可以把遇店记为 a，遇花记为 b，那么 babaabbabbabbbb 就是一个合理的次序。像这样的答案一共有多少种呢？请你计算出所有可能方案的个数（包含题目给出的那一种）。

注意：通过浏览器提交答案。答案是个整数，不要书写任何多余的内容。

解题思路

总共有 5 次遇店和 10 次遇花，合起来是 15 步。由于题目规定最后一次必须是花，因此只需要枚举前 14 步的排列即可，最后一步强制为花。

用一个 14 位的二进制数来表示前 14 步的走法：每一位为 1 表示遇店（酒量翻倍），为 0 表示遇花（酒量减一）。对每一种枚举，模拟整个过程，最后检查店的次数、花的次数以及剩余酒量是否满足条件即可。

因为最后一步固定是花（酒量减 1 后正好为 0），所以模拟到第 14 步结束时，剩余酒量应当为 1，店剩 0 次可用、花剩 0 次可用（即前 14 步中用掉了 5 店 9 花）。

参考代码（C++，类似于暴力枚举）

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include<time.h>
#include<math.h>
using namespace std;


int main(int argc, char* argv[])
{

	// dian为1  hua为0
	int no=2;  //酒量

	int time=0;
	int MAX=pow(2,14);
	for(int i=0;i<MAX;i++)
	{
		no=2;
		int a=5;//dian
		int b=9;//hua
			int ii=i;
		for(int j = 0; j < 14; j++)
		{
			if(no < 0)
			{
				break;
			}

			if(ii%2==0)
			{
				no--;
				b--;
			}
			else
			{
				a--;
				no*=2;
			}
			ii=ii>>1;

			if(a==0&&1==no&&0==b)//因为最后一次 是花 所以 剩余酒量为1
			{
				time++;
			}
		}
	}

	cout<<time;
	cout << "\n  " << clock() << endl;
	return 0;
}