【蓝桥杯逐日一题】分糖果——DFS

分糖果

   蓝桥杯逐日一题 2024-12-24 分糖果 DFS
  标题描述

   两种糖果分别有 9 个和 16 个，要全部分给 7 个小朋友，每个小朋友得到的糖果总数最少为 2 个最多为 5 个，问有多少种差别的分法。糖果必须全部分完。
  只要有此中一个小朋友在两种方案中分到的糖果不完全相同，这两种方案就算作差别的方案。
  解题思路

   虽然这是一道填空题，但是还是要通过代码来实现，结果太大了。
  这是一个分配问题，通过差别的分配个数来找出差别的分发，特别注意的是，这道题中有两种糖果，而且在分的时候只要糖果不完全相同就行；也就是不能将这两种糖果融为一种来算。
  由于糖果种类差别，为了更好地限定递归次数，应该使用人数来判断是否需要竣事递归，那么递归的时候就要摆列糖果的取法了；由于是两种糖果，我们要使用双重循环来摆列每一种糖果，然后递归求取每一个人可获得的糖果数。
  Accepted

1. #include <iostream>
2. using namespace std;
3. int res;
4. void dfs(int u,int tmp1,int tmp2) {
5.     if(u > 7) {
6.         if(!tmp1 && !tmp2) res++;
7.         return ;
8.     }
9.     for(int i = 0;i <= tmp1;i++) {      // 枚举第一种糖果
10.         for(int j = 0;j <= tmp2;j++) {  // 枚举第二种糖果
11.             if(i+j >= 2 && i+j <= 5) {  // 当前这个人的糖果分配可以满足条件
12.                 dfs(u+1,tmp1-i,tmp2-j); // 接着递归下一个人
13.             }
14.         }
15.     }
16. }
17. int main () {
18.     dfs(1,9,16);
19.     cout<<res<<endl;
20.     return 0;
21. }

复制代码

思索

   刚开始写的时候当成一种糖果盘算了，然而这是不对的；这个题的解题关键就是在摆列糖果的取法，而且是分别摆列两种糖果的。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。