题解 | #小红的暑假#

题目链接

小红的暑假

题目描述

小红和她的三位朋友（编号为1, 2, 3）一共有 $3k$ 天暑假。她需要安排每天与其中一位朋友玩。最终的安排需要满足两个条件：

假期结束后，她与每位朋友都恰好玩了 $k$ 天。
她不会连续两天和同一个朋友玩。

请求出满足条件的所有安排方案数，结果对 $10^9 + 7$ 取模。

解题思路

这是一个典型的计数类动态规划问题。我们需要设计的状态要能够同时满足题目中的两个约束条件。

1. 状态定义

为了满足约束条件，我们的状态需要包含以下信息：

已经和每位朋友玩了多少天（用于满足条件1）。
前一天和哪位朋友玩的（用于满足条件2）。

因此，我们可以定义一个四维DP数组： $dp[i][j][l][p]$ 表示在已经过去的 $i+j+l$ 天里，

小红与朋友1玩了 $i$ 天。
小红与朋友2玩了 $j$ 天。
小红与朋友3玩了 $l$ 天。
并且，在第 $i+j+l$ 天（也就是最后一天），她是和朋友 $p$ 一起玩的。其中 $p \in \{1, 2, 3\}$ 。

这个状态的含义是：满足上述条件时的总方案数。

2. 状态转移

我们考虑如何计算 $dp[i][j][l][p]$ 。要想到达这个状态，我们必须从一个总天数为 $(i+j+l-1)$ 的有效状态转移而来。

计算 $dp[i][j][l][1]$ (最后一天和朋友1玩)：这种情况说明，在第 $i+j+l$ 天，小红选择了朋友1。那么，在前 $i+j+l-1$ 天里，她必然是和朋友1玩了 $i-1$ 天，和朋友2、3分别玩了 $j$ 天和 $l$ 天。同时，根据约束2，前一天的朋友不能是1，所以只能是朋友2或朋友3。因此，方案数是前 $i+j+l-1$ 天以朋友2或朋友3结尾的方案数之和。 $dp[i][j][l][1] = (dp[i-1][j][l][2] + dp[i-1][j][l][3]) \pmod{10^9+7}$
计算 $dp[i][j][l][2]$ (最后一天和朋友2玩)：同理，这种状态只能从前一天与朋友1或朋友3玩的状态转移而来。 $dp[i][j][l][2] = (dp[i][j-1][l][1] + dp[i][j-1][l][3]) \pmod{10^9+7}$
计算 $dp[i][j][l][3]$ (最后一天和朋友3玩)：同理，这种状态只能从前一天与朋友1或朋友2玩的状态转移而来。 $dp[i][j][l][3] = (dp[i][j][l-1][1] + dp[i][j][l-1][2]) \pmod{10^9+7}$

3. 初始化 (Base Case)

在第一天，有三种可能：

和朋友1玩： $dp[1][0][0][1] = 1$
和朋友2玩： $dp[0][1][0][2] = 1$
和朋友3玩： $dp[0][0][1][3] = 1$ DP数组的其余所有值初始化为0。

4. 遍历顺序

我们从小到大枚举已经和各位朋友玩的天数。使用三层循环，分别遍历 $i, j, l$ 从 0 到 $k$ 。这样的顺序可以保证在计算 $dp[i][j][l]$ 时，所有依赖的子问题（如 $dp[i-1][j][l]$ ）都已经计算完毕。

5. 最终答案

我们的目标是求出 $3k$ 天的总方案数，其中和每位朋友都玩了 $k$ 天。这对应于状态 $dp[k][k][k]$ 。由于最后一天可以是和任意一位朋友玩，所以最终答案是这三种情况的总和： $Ans = (dp[k][k][k][1] + dp[k][k][k][2] + dp[k][k][k][3]) \pmod{10^9+7}$

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

long long dp[101][101][101][4];

int main() {
    int k;
    cin >> k;

    dp[1][0][0][1] = 1;
    dp[0][1][0][2] = 1;
    dp[0][0][1][3] = 1;

    for (int i = 0; i <= k; ++i) {
        for (int j = 0; j <= k; ++j) {
            for (int l = 0; l <= k; ++l) {
                if (i == 0 && j == 0 && l == 0) continue;
                if (i == 1 && j == 0 && l == 0) continue;
                if (i == 0 && j == 1 && l == 0) continue;
                if (i == 0 && j == 0 && l == 1) continue;

                if (i > 0) {
                    dp[i][j][l][1] = (dp[i-1][j][l][2] + dp[i-1][j][l][3]) % MOD;
                }
                if (j > 0) {
                    dp[i][j][l][2] = (dp[i][j-1][l][1] + dp[i][j-1][l][3]) % MOD;
                }
                if (l > 0) {
                    dp[i][j][l][3] = (dp[i][j][l-1][1] + dp[i][j][l-1][2]) % MOD;
                }
            }
        }
    }

    long long ans = (dp[k][k][k][1] + dp[k][k][k][2] + dp[k][k][k][3]) % MOD;
    cout << ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int MOD = 1_000_000_007;

        long[][][][] dp = new long[k + 1][k + 1][k + 1][4];

        dp[1][0][0][1] = 1;
        dp[0][1][0][2] = 1;
        dp[0][0][1][3] = 1;

        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= k; j++) {
                for (int l = 0; l <= k; l++) {
                    if (i == 0 && j == 0 && l == 0) continue;
                    if (i == 1 && j == 0 && l == 0) continue;
                    if (i == 0 && j == 1 && l == 0) continue;
                    if (i == 0 && j == 0 && l == 1) continue;

                    if (i > 0) {
                        dp[i][j][l][1] = (dp[i-1][j][l][2] + dp[i-1][j][l][3]) % MOD;
                    }
                    if (j > 0) {
                        dp[i][j][l][2] = (dp[i][j-1][l][1] + dp[i][j-1][l][3]) % MOD;
                    }
                    if (l > 0) {
                        dp[i][j][l][3] = (dp[i][j][l-1][1] + dp[i][j][l-1][2]) % MOD;
                    }
                }
            }
        }

        long ans = (dp[k][k][k][1] + dp[k][k][k][2] + dp[k][k][k][3]) % MOD;
        System.out.println(ans);
    }
}

k = int(input())
MOD = 10**9 + 7

dp = [[[[0] * 4 for _ in range(k + 1)] for _ in range(k + 1)] for _ in range(k + 1)]

dp[1][0][0][1] = 1
dp[0][1][0][2] = 1
dp[0][0][1][3] = 1

for i in range(k + 1):
    for j in range(k + 1):
        for l in range(k + 1):
            if i == 0 and j == 0 and l == 0:
                continue
            # 跳过已经初始化的基础情况
            total_days = i + j + l
            if total_days == 1:
                continue

            if i > 0:
                dp[i][j][l][1] = (dp[i-1][j][l][2] + dp[i-1][j][l][3]) % MOD
            if j > 0:
                dp[i][j][l][2] = (dp[i][j-1][l][1] + dp[i][j-1][l][3]) % MOD
            if l > 0:
                dp[i][j][l][3] = (dp[i][j][l-1][1] + dp[i][j][l-1][2]) % MOD

ans = (dp[k][k][k][1] + dp[k][k][k][2] + dp[k][k][k][3]) % MOD
print(ans)

算法及复杂度

算法：动态规划
时间复杂度： $\mathcal{O}(k^3)$ 。我们需要填充一个三维的DP表（第四维是常数大小），填充每个状态的时间是 $\mathcal{O}(1)$ 。
空间复杂度： $\mathcal{O}(k^3)$ 。DP表的大小为 $k \cdot k \cdot k \cdot 4$ 。