动态规划。小豚鼠排排坐。 小艺酱买了一排排格子的小房子nm，她想让k只小豚鼠每只小豚鼠都有自己的房子。 但是为了不浪费空间，她想要小房子的最外圈尽量每行每列都有一只小豚鼠居住。 小艺酱想知道自己有多少种方案安排小豚鼠。输入整数n,m,k。(1<=n,m<=20,0<=k<=nm)输出方案数，答案对1e9+7取模。

动态规划是一种通过拆分问题为子问题的方法来解决复杂问题的算法。

在这道题中，我们可以使用动态规划来求解小豚鼠安排方案数的问题。

首先，我们考虑如何表示状态。在这道题中，我们可以使用二维数组 dp[i][j] 来表示小豚鼠安排方案数，其中 i 表示前 i 行已经安排好了，j 表示已经安排好了 j 只小豚鼠。

接下来，我们考虑如何转移状态。对于 dp[i][j]，它可以从 dp[i-1][j] 转移过来，也可以从 dp[i-1][j-1] 转移过来，因为在第 i 行有两种选择：不安排小豚鼠或者安排一只小豚鼠。

所以，我们可以得到转移方程如下：

dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

最后，我们要求的是 dp[n][k]，因此完整的动态规划代码如下：

int n, m, k;
const int mod = 1e9 + 7;
int dp[25][450];

int main() {
    cin >> n >> m >> k;
    dp[1][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = dp[i-1][j];
            if (j > 0) dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod;
        }
    }
    cout << dp[n][

相关问题

小豚鼠排排坐。 小艺酱买了一排排格子的小房子n*m，她想让k只小豚鼠每只小豚鼠都有自己的房子。 但是为了不浪费空间，她想要小房子的最外圈尽量每行每列都有一只小豚鼠居住。 小艺酱想知道自己有多少种方案安排小豚鼠。输入整数n,m,k。(1<=n,m<=20,0<=k<=n*m)输出方案数，答案对1e9+7取模。

这是一道动态规划的题目。

定义 $dp[i][j][k]$ 表示当前在第 $i$ 行第 $j$ 列，已经有了 $k$ 只小豚鼠，有多少种方案。

初始化：

$dp[1][1][1] = 1$

$dp[1][1][0] = 1$

转移方程：

当 $i = 1$ 时：

$dp[1][j][k] = dp[1][j - 1][k - 1] + dp[1][j - 1][k]$

当 $j = 1$ 时：

$dp[i][1][k] = dp[i - 1][1][k - 1] + dp[i - 1][1][k]$

当 $i, j > 1$ 时：

$dp[i][j][k] = dp[i - 1][j][k - 1] + dp[i - 1][j][k] + dp[i][j - 1][k - 1] + dp[i][j - 1][k]$

最终答案为 $dp[n][m][k]$。

上面的方程也可以写成以下的形式：

$dp[i][j][k] = \sum_{p = 0}^{1} \sum_{q = 0}^{1} dp[i - p][j - q][k - p - q]$

代码如下：

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    // 初始化
    dp[1][1][1] = 1;
    dp[1][1][0] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int l = 0; l <= k; l++)
            {
                if (i == 1)
                {
                    dp[i][j][l] = (dp[i][j - 1][l - 1] + dp[i][j - 1][l]) % mod;
                }
                else if (j == 1)
                {
                    dp[i][j][l] = (dp[i - 1][j][l - 1] + dp[i - 1][j][l]) % mod;
                }
                else
                {
                    dp[i][j][l] = (dp[i - 1][j][l - 1] + dp[i - 1][j][l] + dp[i][j - 1][l - 1] + dp[i][j

Dasha 很喜欢豚鼠，她在 � n 天内要不是买豚鼠，要不是请医生来看豚鼠。 Dasha 和宠物店都无法分辨豚鼠的性别（思考人生），只能在医生来查看豚鼠的时候为这些豚鼠做性别鉴定。 为了豚鼠，Dasha 打算给它们买一些笼子，但宠物店里卖的笼子只能放最多 2 2 只豚鼠。由于她不想让她的豚鼠遭受道德伤害，一个笼子里只能放同一种性别的豚鼠。 求 Dasha 最少需要买多少个笼子。 这个翻译由 @ztrztr 提供

根据题目描述，Dasha 要么买豚鼠，要么请医生来查看豚鼠的性别。而每个笼子只能放同一种性别的豚鼠，最多放 2 只。因此，Dasha 需要确保每个笼子里只有一种性别的豚鼠。

假设 Dasha 要买 x 只雄性豚鼠和 y 只雌性豚鼠，那么她需要至少买 x 个笼子来放置雄性豚鼠，y 个笼子来放置雌性豚鼠。

根据题目要求，x 和 y 都要么是 0，要么是正整数。而且 x + y >= n，因为至少需要 n 只豚鼠。

综上所述，Dasha 最少需要买的笼子数量是 max(x, y) = max(ceil(n/2), floor(n/2)) = ceil(n/2)。其中 ceil(x) 表示不小于 x 的最小整数，floor(x) 表示不大于 x 的最大整数。

因此，Dasha 最少需要买 ceil(n/2) 个笼子。