|
一、题目解读 牛客网288555题要求解决一个组合数学问题：有三位朋友，每天需邀请其中一位参加聚会，但不能连续两天邀请同一位朋友。给定天数n，求满足条件的不同邀请方案总数。题目考察动态规划、状态转移及组合计数，属于中等难度算法题。 二、解题思路：动态规划 + 状态压缩核心思想是将问题分解为子问题，利用动态规划记录中间状态。定义四维dp数组：dp[a][c][last]，表示已邀请朋友1 a次、朋友2 b次、朋友3 c次，且****邀请的是last（1/2/3）的方案数。通过状态转移方程，枚举下一位朋友的选择，避免重复计数。 三、解题步骤1. 初始化：**天可选任意朋友，初始化dp[1][0][0][1]、dp[0][1][0][2]、dp[0][0][1][3]为1。 2. 状态转移循环：遍历所有可能的(a,b,c)组合，若当前状态dp[a][c][last]有效： 枚举下一个朋友next（1/2/3），跳过与last相同的情况。 更新次数：na=a+(next=1), nb=b+(next=2), nc=c+(next=3)。 若次数不超n，累加方案数：dp[na][nb][nc][next] += dp[a][c][last]。 3. 结果计算：最终方案为所有朋友均被邀请n次的状态总和，即dp[n][n][n][1] + dp[n][n][n][2] + dp[n][n][n][3]（取模防止溢出）。 四、代码与注释- #include <iostream>
- #include <vector>
- #include <cstring>
- using namespace std;
- const int MOD = 1e9 + 7; // 取模常数，防止结果溢出
- const int MAX_N = 100; // **天数限制
- // dp[a][b][c][last] 表示选了a次朋友1，b次朋友2，c次朋友3，**选的是last的方案数
- int dp[MAX_N+1][MAX_N+1][MAX_N+1][4];
- int main() {
- int n;
- cin >> n; // 输入天数n
- memset(dp, 0, sizeof(dp)); // 初始化dp数组为0
- // 初始状态：**天可选任意朋友
- dp[1][0][0][1] = 1; // 选朋友1一次，**为1
- dp[0][1][0][2] = 1; // 选朋友2一次，**为2
- dp[0][0][1][3] = 1; // 选朋友3一次，**为3
- 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++;
- 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;
- }
五、总结本题通过动态规划巧妙解决组合限制问题，关键在于四维状态设计（次数+末尾选择）和转移条件的严谨性。优化点包括利用取模运算避免大数溢出，以及跳过无效状态提升效率。掌握此类状态压缩技巧，可应对更多复杂计数问题。
| 
发表于 2025-6-24 20:56:59
