ACdream 暴力專場題解：蘋果分配問題的十重循環暴力破解

題目：小晴天蘋果大豐收 (M 蘋果 N 箱子，箱子相同，允許空箱，求放法數)

這是一個經典的整數分區問題：將 M 寫成至多 N 個正整數之和，順序不計。等價於分區數 p(M, N)。約束 M, N ≤ 10，極小規模，適合暴力枚舉。

核心思路：遞增序列枚舉避免重複

要求後一箱蘋果數 ≥ 前一箱，即生成非遞減序列 a1 ≤ a2 ≤ ... ≤ aN，且 Σai = M。這樣每種分法對應唯一遞增序列，自然去重。

十重循環暴力實現 (N ≤ 10 固定上限)

#include <stdio.h>

int main(void) {
    int T, M, N;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &M, &N);
        int count = 0;

        // i 代表第一箱，i1 第二箱... 最多十層
        for (int i = 0; i <= M; i++) {
            if (N == 1 && i == M) count++;
            for (int i1 = i; N > 1 && i1 <= M; i1++) {
                if (N == 2 && i + i1 == M) count++;
                for (int i2 = i1; N > 2 && i2 <= M; i2++) {
                    if (N == 3 && i + i1 + i2 == M) count++;
                    for (int i3 = i2; N > 3 && i3 <= M; i3++) {
                        if (N == 4 && i + i1 + i2 + i3 == M) count++;
                        for (int i4 = i3; N > 4 && i4 <= M; i4++) {
                            if (N == 5 && i + i1 + i2 + i3 + i4 == M) count++;
                            for (int i5 = i4; N > 5 && i5 <= M; i5++) {
                                if (N == 6 && i + i1 + i2 + i3 + i4 + i5 == M) count++;
                                for (int i6 = i5; N > 6 && i6 <= M; i6++) {
                                    if (N == 7 && i + i1 + i2 + i3 + i4 + i5 + i6 == M) count++;
                                    for (int i7 = i6; N > 7 && i7 <= M; i7++) {
                                        if (N == 8 && i + i1 + i2 + i3 + i4 + i5 + i6 + i7 == M) count++;
                                        for (int i8 = i7; N > 8 && i8 <= M; i8++) {
                                            if (N == 9 && i + i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 == M) count++;
                                            for (int i9 = i8; N > 9 && i9 <= M; i9++) {
                                                if (N == 10 && i + i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 == M) count++;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

複雜度分析

• 最坏情況 N=10, M=10：循環次數約為組合數 C(M+N-1, N-1) = C(19,9) = 92378，極小，瞬間通過。
• 時限 2s，內存 128MB，暴力完全足夠。

進階優化：動態規劃 (DP) 通用解法

若約束擴大 (如 M,N ≤ 1000)，需用 DP：

// dp[i][j] 表示將 i 放入 j 個箱子的方法數
// 遞推：dp[i][j] = dp[i][j-1] + dp[i-j][j]  (至少一個箱子放 1 個 / 每個箱子至少 1 個)
// 邊界：dp[0][j] = 1, dp[i][0] = 0 (i>0)
// 允許空箱等價於將 M+N 個蘋果放入 N 個箱子且每箱至少 1 個
// 即答案 = p(M+N, N) = dp[M+N][N]

但本題 M,N ≤ 10，**暴力十重循環最簡潔、最難出錯、無需推導遞推式**，是競賽中「優美暴力」的典範。

樣例驗證

輸入：1\n7 3 → 輸出 8

8 種分法：
7+0+0, 6+1+0, 5+2+0, 4+3+0,
5+1+1, 4+2+1, 3+3+1, 3+2+2

掌握「非遞減序列枚舉去重」技巧，配合題目約束果斷選擇暴力/DP，是算法競賽實戰的關鍵直覺。