1163排队买票(dfs 深搜）

解题思路:
看到方案数，就想到了 dfs ，而且这道题 M 的值在10以内，所以一般情况下是不会超时的，当时思路一定要清晰，这是做题的关键！这是在勉励自己！！！我第一次做的时候，就没有考虑全面，不知道如何处理相同金额的小孩。
注意事项:

参考代码:

#include<iostream>

using namespace std;

int M, N, K;

int arr[15][2];//arr[i][0]存的是 1元 或 2 元   arr[i][1]存的是当前这个小孩有没有被选上，1 选了，0 没选

int vis = 0;//存 方案数

// m 是当前排了几个小孩， n 是 当前的零钱数

void dfs( int m, int sum)

{

if (m == M)//小孩有 M 个时，就计数

{

vis++;

return;

}

for (int i = 1; i <= M; i++)//遍历寻找符合条件的小孩，而且还要保证 他 前面几次都没有被选过

{

if (arr[i][1] == 0)//保证没被选过

{

if (arr[i][0] == 2 && sum > 0)//零钱有剩余就可以选择零钱是 2元 的小孩

{

arr[i][1] = 1;

dfs( m + 1, sum - 1);

arr[i][1] = 0;//回溯

}

if (arr[i][0] == 1)//零钱是 一元 的小孩肯定能选

{

arr[i][1] = 1;

dfs( m + 1, sum + 1);

arr[i][1] = 0;//回溯

}

}

}

}

int main()

{

cin >> M >> N >> K;

for (int i = 1; i <= M; i++)

{

if (i <= N)

arr[i][0] = 1;

else

arr[i][0] = 2;

}

for (int i = 1; i <= M; i++)//这里是挑选 可以作为第一个的小孩，也就是 一元 的小孩做第一个人

{

if (arr[i][0] == 1)

{

arr[i][1] = 1;//选上

dfs(1, 1);

arr[i][1] = 0;//回溯，因为不止一位 一元 的小孩

}

}

cout << vis << endl;

return 0;

}