牛客网REAL645题：动态规划计算小红的暑假（附完整代码解析）

7天前牛客题解64

一、问题重述与分析

小红有3个朋友，暑假共3n天，每天选择一位朋友游玩，要求：

每个朋友恰好被选择n次
不能连续两天选择同一位朋友

这实际上是一个受限排列组合问题，需要计算所有满足条件的序列数量。

二、动态规划解法详解

状态设计

采用四维dp 数组： dp[a][b][c][last] 表示：

已选择朋友A a次
已选择朋友B b次
已选择朋友C c次
最后选择的朋友是last（0=A,1=B,2=C）

状态转移

对于每个状态，考虑前一天的选择：

如果今天选A，那么前一天只能选B或C
如果今天选B，那么前一天只能选A或C
如果今天选C，那么前一天只能选A或B

转移方程：

dp[a][b][c][0] = dp[a-1][b][c][1] + dp[a-1][b][c][2]
dp[a][b][c][1] = dp[a][b-1][c][0] + dp[a][b-1][c][2] 
dp[a][b][c][2] = dp[a][b][c-1][0] + dp[a][b][c-1][1]

初始化

第一天可以选择任意朋友：

dp[1][0][0][0] = 1  // 第一天选A
dp[0][1][0][1] = 1  // 第一天选B
dp[0][0][1][2] = 1  // 第一天选C

结果计算

最终结果是所有朋友都被选择n次的情况之和：

result = dp[n][n][n][0] + dp[n][n][n][1] + dp[n][n][n][2]

三、优化思考

实际可以压缩状态到三维，因为a+b+c等于当前总天数。但四维状态更直观易于理解，适合教学。

四、完整代码

#include <iostream>
#include <vector>
using namespACe std;
const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    
    // dp[a][b][c][last] 表示用了a次A，b次B，c次C，最后一个是last的方案数
    // last取值0(A),1(B),2(C)
    vector<vector<vector<vector<int>>>> dp(
        n+1, vector<vector<vector<int>>>(
            n+1, vector<vector<int>>(
                n+1, vector<int>(3, 0))));
    
    // 初始化：第一天可以选择任意朋友
    dp[1][0][0][0] = 1;
    dp[0][1][0][1] = 1;
    dp[0][0][1][2] = 1;
    
    for(int a = 0; a <= n; ++a) {
        for(int b = 0; b <= n; ++b) {
            for(int c = 0; c <= n; ++c) {
                if(a + b + c < 2) continue; // 总天数至少2天
                for(int last = 0; last < 3; ++last) {
                    if(last == 0 && a == 0) continue;
                    if(last == 1 && b == 0) continue;
                    if(last == 2 && c == 0) continue;
                    
                    int &val = dp[a][b][c][last];
                    // 前一天不能和今天选同一个人
                    if(last == 0 && a > 0) {
                        val = (val + dp[a-1][b][c][1]) % MOD;
                        val = (val + dp[a-1][b][c][2]) % MOD;
                    }
                    if(last == 1 && b > 0) {
                        val = (val + dp[a][b-1][c][0]) % MOD;
                        val = (val + dp[a][b-1][c][2]) % MOD;
                    }
                    if(last == 2 && c > 0) {
                        val = (val + dp[a][b][c-1][0]) % MOD;
                        val = (val + dp[a][b][c-1][1]) % MOD;
                    }
                }
            }
        }
    }
    
    // 最终结果是三种最后选择情况的加和
    int res = 0;
    for(int last = 0; last < 3; ++last) {
        res = (res + dp[n][n][n][last]) % MOD;
    }
    cout << res << endl;
    return 0;
}