【搜索与回溯算法】售货员的烦恼 (Standard IO)

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目描述:

一间冰淇淋商店刚刚开张，外面有2×N个人购买1元的冰淇淋，其中一半人拿着1张2元人民币，另一半人拿一张1元人民币。售货员很粗心，没有准备零钱，要使出售过程中不发生找钱困难的问题，这2×N个人应该如何排队？请你帮售货员找出所有方案数量的总和。

输入:

一个整数N(N≤15)。

输出:

方案总数M。

样例输入:

4
样例输出:

14
这是第五道题。小航看了题，很快开始了思考。

小航想道（思路）：

1.可用模拟的方法来做

2.从第一人开始，依次模拟，直到到达二分之一n

3.带一元钱的应排在带二元钱的人之前，因此方案中，已付款的带一元钱的人数必须等于或小于已付款且带二元钱的人数。否则，立即返回。

4.当超过界点（即大于二倍的n），也要马上返回

5.可以用两个全局变量储存“已付款的带一元钱的人数”与“已付款的带二元钱的人数”，用局部变量表示当前已有多少人付款

小航写道（程序）

#include<iostream>
using namespace std;
int n,sum,p1,p2;
void dg(int x)
{
    if(p1>n||p2>n)
    {
        return;
    }
    if(x==2*n)
    {
        sum++;
        return;
    }
    else
    {
        if(p2>p1)
        {
            return;
        }
        else
        {
            p1++;
            dg(x+1);
            p1--;
            p2++;
            dg(x+1);
            p2--;
        }
    }
}
int main()
{
    cin>>n;
    dg(0);
    cout<<sum;
}

很显然，结果是：

    100分！

但是，时间不多，小航没时间写完第五题，只好乱写一通。一个

显现显现出来！

“叮——”比赛结束，小亮以500分的成绩进入前100。

“同学们，没考好不要灰心，因为我们一同走进“深度搜索基础训练“，踏入c++算法殿堂！”主持人说，“对了，要记得写比赛总结，回家后要改题！”

小提示：
比赛时要注意时间，不要犯下和小航一样的错误；比赛后最好写比赛总结，并且改题，这样才会更好地进步！