LQ0190 李白打酒【填空题】

题目来源：蓝桥杯2014初赛 C++ B组C题

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

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

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

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

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

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

问题分析
一种方法是用DFS来实现。
另外一种方法是用二进制编码枚举，从低位到高位表示过程，1表示花，0表示店，再进行统计判定。

AC的C语言程序（DFS）如下：

/* LQ0190 李白打酒 */

#include 

int dfs(int s, int f, int n)
{
    if (s > 5 || f > 10 || n < 0)
        return 0;
    else if (s == 5 && f == 10 - 1 && n == 1)
        return 1;
    else
        return dfs(s + 1, f, n * 2) + dfs(s, f + 1, n - 1);
}

int main()
{
    printf("%d\n", dfs(0, 0, 2));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

AC的C语言程序（二进制位枚举）如下：

/* LQ0190 李白打酒 */

#include 

#define N 15

int main()
{
    int start = 1 << (N - 1);
    int end = (start << 1) - 1;

    int cnt = 0;
    for (int i = start; i <= end; i++) {
        int s = 0, f = 0, al = 2;
        for (int j = 0; j < N - 1; j++) {
            if ((i >> j) & 1) {
                if (++f > 10) break;
                al--;
            } else {
                if (++s > 5) break;
                al *= 2;
            }
        }
        if (f == (10 - 1) && s == 5 && al == 1)
            cnt++;
    }

    printf("%d\n", cnt);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31