题解 | #小红的暑假#

题目链接

题目描述

小红和她的三个朋友们都有 $n$ 天的暑假，她在暑假每天都找了其中一个朋友玩。暑假结束后，小红惊喜的发现，她跟每一个朋友都恰好玩了 $n$ 天。小红现在已经忘记了每天去找哪个朋友玩了，但她还记得没有连续 $2$ 天都跟同一个朋友玩。小红想知道有多少种可能的找朋友玩的序列。

输入:

一行输入一个整数 $n$

输出:

输出一个整数表示答案。由于答案可能很大，输出答案对 $998244353$ 取模的结果

解题思路

这是一个动态规划问题，可以通过以下步骤解决：

关键发现：
- 每个朋友都恰好玩了 $n$ 天
- 不能连续两天和同一个朋友玩
- 总天数是 $3n$ （三个朋友各 $n$ 天）
解题策略：
- 使用动态规划数组记录状态
- dp[i][j][k][l] 表示第一个朋友玩了i天，第二个朋友玩了j天，第三个朋友玩了k天，最后一个玩的是第l个朋友时的方案数
- 按天数递推，每次选择一个不同于上一个的朋友
具体步骤：
- 初始化dp数组，设置初始状态
- 按天数递推，每次尝试选择不同的朋友
- 最后统计所有可能的结果

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long dp[n + 1][n + 1][n + 1][3];
    memset(dp, 0, sizeof(dp));
    dp[1][0][0][0] = 1;
    dp[0][1][0][1] = 1;
    dp[0][0][1][2] = 1;
    for (int day = 1; day < 3 * n; day++) {
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                int k = day - i - j;
                if (k < 0 || k > n) continue;
                if (i + 1 <= n) {
                    dp[i + 1][j][k][0] = (dp[i + 1][j][k][0] + dp[i][j][k][1] + dp[i][j][k][2]) % mod;
                }
                if (j + 1 <= n) {
                    dp[i][j + 1][k][1] = (dp[i][j + 1][k][1] + dp[i][j][k][0] + dp[i][j][k][2]) % mod;
                }
                if (k + 1 <= n) {
                    dp[i][j][k + 1][2] = (dp[i][j][k + 1][2] + dp[i][j][k][0] + dp[i][j][k][1]) % mod;
                }
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < 3; i++) {
        ans = (ans + dp[n][n][n][i]) % mod;
    }
    cout << ans << '\n';

    return 0;
}

import java.util.*;

public class Main {
    static final int mod = 1000000007;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long[][][][] dp = new long[n + 1][n + 1][n + 1][3];
        dp[1][0][0][0] = 1;
        dp[0][1][0][1] = 1;
        dp[0][0][1][2] = 1;
        
        for (int day = 1; day < 3 * n; day++) {
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= n; j++) {
                    int k = day - i - j;
                    if (k < 0 || k > n) continue;
                    if (i + 1 <= n) {
                        dp[i + 1][j][k][0] = (dp[i + 1][j][k][0] + dp[i][j][k][1] + dp[i][j][k][2]) % mod;
                    }
                    if (j + 1 <= n) {
                        dp[i][j + 1][k][1] = (dp[i][j + 1][k][1] + dp[i][j][k][0] + dp[i][j][k][2]) % mod;
                    }
                    if (k + 1 <= n) {
                        dp[i][j][k + 1][2] = (dp[i][j][k + 1][2] + dp[i][j][k][0] + dp[i][j][k][1]) % mod;
                    }
                }
            }
        }
        
        long ans = 0;
        for (int i = 0; i < 3; i++) {
            ans = (ans + dp[n][n][n][i]) % mod;
        }
        System.out.println(ans);
    }
}

n = int(input())
mod = 1000000007

# 创建4维dp数组
dp = [[[[0]*3 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
dp[1][0][0][0] = 1
dp[0][1][0][1] = 1
dp[0][0][1][2] = 1

for day in range(1, 3 * n):
    for i in range(n + 1):
        for j in range(n + 1):
            k = day - i - j
            if k < 0 or k > n:
                continue
            if i + 1 <= n:
                dp[i + 1][j][k][0] = (dp[i + 1][j][k][0] + dp[i][j][k][1] + dp[i][j][k][2]) % mod
            if j + 1 <= n:
                dp[i][j + 1][k][1] = (dp[i][j + 1][k][1] + dp[i][j][k][0] + dp[i][j][k][2]) % mod
            if k + 1 <= n:
                dp[i][j][k + 1][2] = (dp[i][j][k + 1][2] + dp[i][j][k][0] + dp[i][j][k][1]) % mod

ans = sum(dp[n][n][n]) % mod
print(ans)

算法及复杂度

算法：动态规划
时间复杂度： $\mathcal{O}(n^3)$ - 需要遍历三个维度的状态
空间复杂度： $\mathcal{O}(n^3)$ - 需要存储四维dp数组

注意：

需要使用long long/long类型避免整数溢出
注意取模运算的正确使用
初始状态的设置很重要
状态转移时需要考虑所有可能的前一个状态