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

我们可以把小豚鼠的安排看成一个二维01矩阵，1表示有小豚鼠，0表示没有。因为小艺酱想要最外圈尽量每行每列都有一只小豚鼠居住，所以我们可以先确定这个01矩阵的边框，然后再考虑其他的格子。

我们先来看如何确定边框。因为边框的每一行和每一列都要有一只小豚鼠，所以我们可以先枚举有多少行和列是由小豚鼠占满的。这样就可以确定这个01矩阵的边框了。

现在我们要考虑剩余的格子。我们可以先把这些格子看成一个新的01矩阵，然后求出这个新的01矩阵有多少种填法。这个新的01矩阵有多少种填法可以用dp来求解。设dp[i][j][k]表示填了i行j列，还剩k只小豚鼠的方案数。那么可以得到dp的转移方程：dp[i][j][k] = dp[i-1][j][k-1] + dp[i][j-1][k-1]。

综上，我们可以写出以下代码：

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

int main() {
cin >> n >> m >> k;
dp[0][0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int l = 0; l <= k; l++) {
if (i > 0

相关问题

小豚鼠排排坐。 小艺酱买了一排排格子的小房子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) 个笼子。