POJ

POJ1664 放苹果

題目連結

  • 題意：把 $M$ 个同樣的蘋果放在 $N$ 个同樣的盤子里，允許有的盤子空着不放，問共有多少種不同的分法？($1\leq N,M \leq 10$)(1 1 5 和 1 5 1 視為一種)。
  • 題解：遞迴求解，將答案存在 $V$，$V_1<V_2<V_3<…$，這樣就不會求到重複的答案。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    #pragma GCC optimize(2)
    #include <iostream>
    #include <vector>
    using namespace std;
    const int INF = 1e9;
    const int MXN = 0;
    const int MXV = 0;
    #define MP make_pair
    #define PB push_back
    #define F first
    #define S second
    #define FOR(i, L, R) for (int i = L; i != (int)R; ++i)
    #define FORD(i, L, R) for (int i = L; i != (int)R; --i)
    #define IOS                                                                    \
        cin.tie(NULL);                                                          \
        cout.tie(NULL);                                                         \
        ios_base::sync_with_stdio(false);
    int n, m;
    int ans;
    vector<int> v(10);

    void dfs(int _m, int _n)
    {
        // cout << _m << ' ' << _n << '\n';
        if (_n == n)
        {
            return;
        }
        if (_m == m)
        {
            ++ans;
            return;
        }
        if (_n == 0 || v[_n] < v[_n - 1])
        {
            ++v[_n];
            dfs(_m + 1, _n);
            --v[_n];
        }
        dfs(_m, _n + 1);
    }

    int main()
    {
        IOS;
        int t;
        cin >> t;
        while (t--)
        {
            cin >> m >> n;
            ans = 0;
            dfs(0, 0);
            cout << ans << '\n';
        }
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts