ZSTUOJ 三只小猪

题目描述

这日，快码佳编四兄弟姐妹来到了一个山脚下，只听一个老奶奶给两个孙子讲故事。
你听说过三只小猪的故事吗？这是一个经典的故事。很久很久以前，有三只小猪。第一只小猪用稻草建的房子，第二个小猪用木棍建的房子，第三个小猪则使用砖做为材料。一只大灰狼想吃掉它们并吹倒了稻草和木棍建的房子。但是砖盖的房子很结实，狼最终也没有破坏掉，最后小猪们战胜了大灰狼并把它尾巴烧掉了。
为了自己的安全，小猪们又建造了一个新砖房。但是现在问题出现了，怎样把三个小猪分配到两个房子里呢？第三只小猪是三只小猪中最聪明的一只，为了不浪费任何一个房子，它总共考虑了三种方案，如下图
Alt

但是将来怎么办呢？”第三只小猪知道将来随着成员的增多，它们将会盖更多的房子。它想知道给定了房子和猪的数目后，房子的分配方案有多少，但这个问题对于它来说，很明显有点难了，你能帮小猪解决这个问题吗？

输入

多组测试，每组仅有一行，包含两个整数n和m，分别表示小猪的数目和房间数（1≤n≤20，0≤m≤20）

输出

每组输出一行，仅一个整数，表示将n只小猪安置在m个房间且没有房间空闲的方案数。

样例输入

4 2

样例输出

7

思路

公式推导

定义

  • dp[i][j] 表示将 i 只小猪分配到 j 个房间且没有房间空闲的方案数。

状态转移

  1. 第一种情况：将其中的一只小猪放入已有的 j 个房间之一

    • 假设我们已经把 i-1 只小猪分配到了 j 个房间。
    • 第 i 只小猪可以选择放入这 j 个房间中的任何一个。
    • 方案数：

  2. 第二种情况：让其中的一只小猪独立占用一个新房间

    • 假设我们已经把 i-1 只小猪分配到了 j-1 个房间。
    • 第 i 只小猪会独立占用一个新房间，且总房间数增加到 j 。
    • 方案数：

合并结果

由于上述两种情况是互斥的，总方案数就是它们的和：

初始条件

  1. 当 i < j 时：一定有空的房间，不合题意， dp[i][j] = 0 。
  2. 当 j = 1 时：所有的小猪都必须挤在一个房间， dp[i][1] = 1 。
  3. 当 i = j 时：每个小猪都必须独占一个房间， dp[i][j] = 1 。

代码

注意：

  • 初始化循环的结束边界是 n 还是 m
  • 要开 long long，否则 AC 60%
#include <iostream>
using namespace std;

long long dp[30][30];

long long solve(int n, int m) {
    if (n < m) return 0;
    for (int i = 1; i <= n; ++i) dp[i][1] = 1;
    for (int j = 1; j <= m; ++j) dp[j][j] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }
    return dp[n][m];
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        cout << solve(n, m) << endl;
    }
}