Powered by:NEFU AB-IN

Link

3428. 放苹果

• 题意

  把 M 个同样的苹果放在 N 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？
  盘子相对顺序不同，例如 5，1，1 和 1，5，1 算作同一种分法。

• 思路

  整数划分板子题

  做这题之前可以回顾一下计数类 DP 中的整数划分问题，二者存在一定的相似性。

  状态表示：dp[i][j]

  集合：所有总和是 i，且恰好放在 j 个盘子的方案。

  属性：分法数量

  状态计算：

  方案中最小值是1：去掉一个1，即f[i-1, j-1]

  方案中最小值大于1：每个数都减去1，即f[i-j, j]

  通过上述两种情况，可得状态转移方程：f[i, j] = f[i-1, j-1] + f[i-j, j]

  通过该方式进行状态计算，可以确保 n 个盘子中的苹果数满足 $n1\ge n2\ge \dots \ge nkn1\ge n2\ge \dots \ge nk$。由于该特性，可以确保不重不漏。

  边界条件：dp[0][0] = 1，即 0 个苹果放 0 个盘子中的方案数为1。

  因为允许有些盘子空着不放，所以最终的答案即为：f[m][1]+f[m][2]+...+f[m][n]

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-08-04 17:01:35
  * @FilePath: \Acwing\3428\3428.cpp
  * @LastEditTime: 2022-08-06 01:53:03
  */
  #include 
  using namespace std;
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(0);                                                                                                        \
      cout.tie(0)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int INF = INT_MAX;
  const int N = 1e6 + 10;
  
  signed main()
  {
      IOS;
      int m, n;
      while (cin >> m >> n)
      {
          vector<vector<int>> dp(11, vector<int>(11, 0));
          // m个放进n个盘子
          dp[0][0] = 1;
          for (int i = 1; i <= m; ++i)
          {
              for (int j = 1; j <= i; ++j)
              {
                  dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
              }
          }
          int res = 0;
          for (int j = 1; j <= n; j++)
          {
              res += dp[m][j];
          }
          cout << res << '\n';
      }
      return 0;
  }
  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