【蓝桥杯每日一题】分糖果——DFS
分糖果
蓝桥杯每日一题 2024-12-24 分糖果 DFS
题目描述
两种糖果分别有 9 个和 16 个，要全部分给 7 个小朋友，每个小朋友得到的糖果总数最少为 2 个最多为 5 个，问有多少种不同的分法。糖果必须全部分完。
只要有其中一个小朋友在两种方案中分到的糖果不完全相同，这两种方案就算作不同的方案。
解题思路
虽然这是一道填空题，但是还是要通过代码来实现，结果太大了。
这是一个分配问题，通过不同的分配个数来找出不同的分发，特别注意的是，这道题中有两种糖果，而且在分的时候只要糖果不完全相同就行；也就是不能将这两种糖果融为一种来算。
由于糖果种类不同，为了更好地限定递归次数，应该使用人数来判断是否需要结束递归，那么递归的时候就要枚举糖果的取法了；由于是两种糖果，我们要使用双重循环来枚举每一种糖果，然后递归求取每一个人可获得的糖果数。
Accepted
#include <iostream>
using namespace std;
int res;
void dfs(int u,int tmp1,int tmp2) {
if(u > 7) {
if(!tmp1 && !tmp2) res++;
return ;
}
for(int i = 0;i <= tmp1;i++) { // 枚举第一种糖果
for(int j = 0;j <= tmp2;j++) { // 枚举第二种糖果
if(i+j >= 2 && i+j <= 5) { // 当前这个人的糖果分配可以满足条件
dfs(u+1,tmp1-i,tmp2-j); // 接着递归下一个人
}
}
}
}
int main () {
dfs(1,9,16);
cout<<res<<endl;
return 0;
}
思考
刚开始写的时候当成一种糖果计算了，然而这是不对的；这个题的解题关键就是在枚举糖果的取法，并且是分别枚举两种糖果的。