题目链接:http://120.78.162.102/problem.php?id=6250
时间限制: 1 Sec  内存限制: 128 MB

题目描述

改编自猫腻所著的同名小说《将夜》目前正在火热开播，其中男主角宁缺在考书院二层楼时遇一题“那年春，夫子出国游历，遇桃山美酒，遂寻径登山赏桃品酒，一路摘花饮酒而行，始斩一斤桃花，饮一壶酒，后夫子惜酒，故再斩一斤桃花，只饮半壶酒，再斩一斤桃花，饮半半壶酒，如是而行……至山顶，夫子囊中酒尽，惘然四顾，问：夫子一共斩了几斤桃花，饮了几壶酒？”而当我们的男主角宁缺看到这道题目时，更是直接来了句“谁出的这道题，太二了”，紧接着就提笔写下了“夫子饮二壶酒，斩尽满山桃花”后直接就交卷走人了赢得书院弟子的大赞。
今夫子再次游历，他提着酒壶，从出院出来，酒壶中有酒2斗，他边走边唱：

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

这一路上，他一共遇到店M（0<M<=10）次，遇到花N（0<M<=10）次，已知最后一次遇到的是花，他正好把酒喝光了。
请计算夫子遇到店和花的合理的次序种数。
可以把遇店记为a，遇花记为b，如果M=5，N=10。则：babaabbabbabbbb 就是合理的次序之一。

输入

M、N分别为遇到店和花的次数.

输出

所有可能店和花次序方案的个数.

样例输入

5 10

样例输出

14

解题思路

DFS走一波。。。

#include <stdio.h>
int ans, m, n;
void DFS(int s, int ms, int ns)
{
    if (ms + ns >= m + n)
    {
        if (!s)
            ans++;
        return ;
    }
    if (s <= 0)
        return ; 
    if (ms < m) DFS(s * 2, ms + 1, ns);
    if (ns < n) DFS(s - 1, ms, ns + 1);
}
int main()
{
    while (~scanf("%d%d", &m, &n))
    {
        ans = 0;
        DFS(2, 0, 0);
        printf("%d\n", ans);
    }
    return 0;
}