[Luogu 2386]放苹果

Description

题库链接

把 \(n\) 个同样的苹果放在 \(m\) 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分发。多测，数据组数 \(t\)。

\(1\leq m,n\leq 10, 1\leq t\leq 20\)

Solution

康复训练 \(\times 3\)。

下午给学弟讲课时发现了这样一道题...数据完全可以出到 \(O(n^2)\) 。

我们记 \(f_{i,j}\) 为 \(i\) 个苹果放在 \(j\) 个盘子中的方案数。显然边界条件为 \(\forall i,f_{0,i}=1\)，理由是没有苹果时局面只有一种，即任何盘子都为空。

要注意到这样一个性质，由于盘子均相同，所以 \(f_{i,j}=f_{i,i},j>i\)。

对于 \(\text{DP}\) 方程，考虑第 \(j\) 个盘子怎么放。

1. 若第 \(j\) 个盘子不放苹果，那么只需考虑 \(i\) 个苹果放在 \(j-1\) 个盘子中的方案数，即 \(f_{i,j-1}\)；
2. 若第 \(j\) 个盘子放苹果，由常规套路 \(\text{DP}\) 时由无序变有序，盘子放苹果数单调递减。那么如果最后一个盘子都有苹果，则所有盘子都有苹果。我们将每个盘子中的苹果数均 \(-1\)，就变成了一般情况。此时方案数为 \(f_{i-j,j}\)。

综上方程为 \(f_{i,j}=f_{i,j-1}+f_{i-j,j}\)。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 50;

int f[N][N], n, m, t;

int main() {

    for (int i = 0; i < 50; i++) f[0][i] = 1;

    for (int i = 1; i < 50; i++)

        for (int j = 1; j < 50; j++) {

            if (j > i) f[i][j] = f[i][i];

            else f[i][j] = f[i][j-1]+f[i-j][j];

        }

    scanf("%d", &t);

    while (t--) {

        scanf("%d%d", &m, &n);

        printf("%d\n", f[m][n]);

    }

    return 0;

}