分糖果

藍橋杯每日一題 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;
}

思考

剛開始寫的時候當成一種糖果計算了，然而這是不對的；這個題的解題關鍵就是在枚舉糖果的取法，并且是分別枚舉兩種糖果的。