牛客288555题：朋友选择问题的四维DP解法详解

2天前牛客题解53

一、问题理解

牛客288555题要求计算选择朋友的合法排列方案数。题目规定：

有3个朋友，每个朋友要被选择恰好n次
不能连续两天选择同一个朋友
结果需要对1e9+7取模

二、算法核心：四维动态规划

我们使用四维dp 数组来记录状态：

前三维分别记录三个朋友被选择的次数
第四维记录最后一次选择的朋友编号

三、完整代码实现（带注释）

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MOD = 1e9 + 7;  // 题目要求的模数
const int MAX_N = 100;    // 题目给定的n的最大值

// dp[a][b][c][last] 表示已经选了a次朋友1，b次朋友2，c次朋友3，最后选的是last(1/2/3)的方案数
int dp[MAX_N+1][MAX_N+1][MAX_N+1][4];

int main() {
    int n;
    cin >> n;
    
    memset(dp, 0, sizeof(dp));  // 初始化DP数组
    
    // 初始状态：第一天可以选择任意一个朋友
    dp[1][0][0][1] = 1;  // 第一天选朋友1
    dp[0][1][0][2] = 1;  // 第一天选朋友2
    dp[0][0][1][3] = 1;  // 第一天选朋友3
    
    // 四重循环填充DP表
    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 == 0) continue;  // 跳过全0的初始状态
                
                for (int last = 1; last <= 3; ++last) {
                    if (dp[a][b][c][last] == 0) continue;  // 跳过无效状态
                    
                    // 尝试选择下一个朋友
                    for (int next = 1; next <= 3; ++next) {
                        if (next == last) continue; // 不能连续选同一个朋友
                        
                        // 计算新的选择次数
                        int na = a, nb = b, nc = c;
                        if (next == 1) na++;
                        else if (next == 2) nb++;
                        else nC++;
                        
                        // 确保不超过n次选择
                        if (na <= n && nb <= n && nc <= n) {
                            dp[na][nb][nc][next] = (dp[na][nb][nc][next] + dp[a][b][c][last]) % MOD;
                        }
                    }
                }
            }
        }
    }
    
    // 汇总结果：所有朋友都被选了n次的总和
    int result = 0;
    for (int last = 1; last <= 3; ++last) {
        result = (result + dp[n][n][n][last]) % MOD;
    }
    
    cout << result << endl;
    return 0;
}