烤鸡怎么烤才美味？试试「递归」~【CSP-J复习】

高山

给你一只烤鸡

现在你要开始放调料了

问顾客对烤鸡需要一定的美味程度

你有多少种搭配的方案呢？具体如何搭配呢？

（强烈建议所有烧烤店学习C++）

高山

这题是一道爽题
如果在复赛，想不出其他方案了

直接写「10层for循环」也是可以直接AC的选择
建议做题时，也要选择合适的方法哦~

FishC

思路：递归 = 每层决定一种配料放几克

把 10 种配料看成 10 层决策。第 k 层选 1、2、3 克，同时记录当前总美味值 sum。

当 k == 11 时，说明 10 种配料都选完了，如果 sum == n，就保存这一组方案。

因为每次从 1 到 3 顺序尝试，所以天然按字典序得到方案。

注意

每种配料最少 1 克，10 种最少 10 克；最多 3 克，10 种最多 30 克。  
所以 n < 10 或 n > 30 时直接输出 0。

先搜索并保存所有方案，最后先输出方案总数，再输出每种方案。

代码

1. 
   
2. #include <bits/stdc++.h>
   
3. using namespace std;
   
4. 
   
5. int n, a[11];
   
6. int ans[60000][11];
   
7. int cnt = 0;
   
8. 
   
9. void dfs(int k, int sum) {
   
10.     if (sum > n) return; // 剪枝：已经超过 n，不用继续
    
11. 
    
12.     if (k == 11) {
    
13.         if (sum == n) {
    
14.             for (int i = 1; i <= 10; i++) {
    
15.                 ans[cnt][i] = a[i];
    
16.             }
    
17.             cnt++;
    
18.         }
    
19.         return;
    
20.     }
    
21. 
    
22.     for (int i = 1; i <= 3; i++) {
    
23.         a[k] = i;
    
24.         dfs(k + 1, sum + i);
    
25.     }
    
26. }
    
27. 
    
28. int main() {
    
29.     cin >> n;
    
30. 
    
31.     if (n < 10 || n > 30) {
    
32.         cout << 0 << endl;
    
33.         return 0;
    
34.     }
    
35. 
    
36.     dfs(1, 0);
    
37. 
    
38.     cout << cnt << endl;
    
39. 
    
40.     for (int i = 0; i < cnt; i++) {
    
41.         for (int j = 1; j <= 10; j++) {
    
42.             cout << ans[i][j] << " ";
    
43.         }
    
44.         cout << endl;
    
45.     }
    
46. 
    
47.     return 0;
    
48. }
    

复制代码

为什么不会漏？

每个位置都试了 1、2、3，相当于把所有 10 种配料的组合都走了一遍。  
只要总和等于 n，就保存下来。最多 3^10 = 59049 种，数组开 60000 够用。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

FishC

高山 发表于 2026-09-23 06:11
这题是一道爽题
如果在复赛，想不出其他方案了

直 ...

说得对，这题确实是「爽题」。

每种配料只有 1~3 克，一共 10 种，总情况只有 3^10 = 59049 种。就算写 10 层 for 循环暴力枚举，也完全能 AC。

不过要注意：

1. 输出顺序要求字典序。只要第 1 种到第 10 种配料都从 1 到 3 枚举，得到的就是字典序。
2. 第一行要先输出方案总数，再输出具体方案。所以要么先统计一遍，要么把方案存下来。

10 层 for 循环核心大概是这样：

1. 
   
2. int a[11], n, cnt = 0;
   
3. cin >> n;
   
4. 
   
5. if (n < 10 || n > 30) {
   
6.     cout << 0;
   
7.     return 0;
   
8. }
   
9. 
   
10. for (a[1] = 1; a[1] <= 3; a[1]++)
    
11. for (a[2] = 1; a[2] <= 3; a[2]++)
    
12. for (a[3] = 1; a[3] <= 3; a[3]++)
    
13. for (a[4] = 1; a[4] <= 3; a[4]++)
    
14. for (a[5] = 1; a[5] <= 3; a[5]++)
    
15. for (a[6] = 1; a[6] <= 3; a[6]++)
    
16. for (a[7] = 1; a[7] <= 3; a[7]++)
    
17. for (a[8] = 1; a[8] <= 3; a[8]++)
    
18. for (a[9] = 1; a[9] <= 3; a[9]++)
    
19. for (a[10] = 1; a[10] <= 3; a[10]++) {
    
20.     int sum = 0;
    
21.     for (int i = 1; i <= 10; i++) sum += a[i];
    
22.     if (sum == n) cnt++;
    
23. }
    
24. 
    
25. cout << cnt << endl;
    
26. 
    
27. // 然后同样的 10 层循环再写一遍，遇到 sum == n 就输出方案
    

复制代码

虽然能过，但写两遍 10 层循环太累，也容易漏括号。所以更推荐用递归 DFS，把「第 k 种配料」当成一层，递归到第 11 层判断，代码短、好调，还能剪枝。

总结：比赛时优先 DFS，实在不会，10 层 for 循环也能保底 AC。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

I会成功

牛

sunshine_8205

菠萝芒果蜜

空python

厉害！

18770897845

犇犇犇