题目分析

题意简述

本题输入一系列正整数 $n$，当输入的 $n$ 小于等于 $0$ 时程序结束。对于每个正整数 $n$，需要根据特定的动态规划规则计算出一个结果。具体是通过一个三维数组 $s$ 来存储中间状态，最终输出每个 $n$ 对应的 $s[n][i][3]$（$i$ 从 $1$ 到 $4$）的总和。

输入

• 多组测试用例，每组为一个正整数 $n$。
• 当输入的 $n$ 小于等于 $0$ 时，程序终止。

输出

对于每组输入的正整数 $n$，输出格式为 “n: 结果”，其中结果是 $\sum_{i = 1}^{4}s[n][i][3]$。

解题思路

动态规划数组初始化

定义一个三维数组 $s[18][5][4]$ 来存储中间状态。对于 $n = 1$ 的情况进行初始化：

• 当 $i = 1$ 或 $i = 4$ 时，$s[1][i][0] = 1$，$s[1][i][1] = 0$，$s[1][i][2] = 0$，$s[1][i][3] = 0$。
• 当 $i = 2$ 或 $i = 3$ 时，$s[1][i][0] = 0$，$s[1][i][1] = 1$，$s[1][i][2] = 0$，$s[1][i][3] = 0$。

动态规划递推

通过递归函数 dp 进行动态规划递推，从 $n = 2$ 开始计算 $s[n][i][j]$ 的值。递推公式根据不同的 $i$ 和 $j$ 组合有不同的计算方式，例如：

• $s[x][1][0]=s[x - 1][1][0]$
• $s[x][1][1]=s[x - 1][1][1]+s[x - 1][2][1]+s[x - 1][3][1]$ 以此类推，根据上一轮的状态计算当前轮的状态。

结果计算与输出

对于每个输入的正整数 $n$，计算 $\sum_{i = 1}^{4}s[n][i][3]$ 的值，并将结果以 “n: 结果” 的格式输出。

代码实现

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

int countValidLocks(int n) {
    if (n < 3) return 0; // 至少需要3个槽才能满足条件
    
    // 动态规划计算不满足条件1的排列数（没有相邻高度差为3）
    // dp[i][j] 表示前i个槽，最后一个槽高度为j的合法排列数
    vector<vector<int> > dp(n + 1, vector<int>(5, 0));
    for (int j = 1; j <= 4; ++j) {
        dp[1][j] = 1;
    }
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= 4; ++j) {
            for (int k = 1; k <= 4; ++k) {
                if (abs(j - k) != 3) {
                    dp[i][j] += dp[i - 1][k];
                }
            }
        }
    }
    int noDiff3 = 0;
    for (int j = 1; j <= 4; ++j) {
        noDiff3 += dp[n][j];
    }
    
    // 计算不满足条件2的排列数（少于3种高度）
    int singleHeight = 4; // 所有槽高度相同，有4种可能
    int twoHeights = 0;
    for (int mask = 1; mask < (1 << 4); ++mask) {
        if (__builtin_popcount(mask) == 2) {
            int cnt = 1;
            for (int i = 0; i < n; ++i) {
                cnt *= 2;
            }
            twoHeights += (cnt - 2);
        }
    }
    
    // 计算不满足条件3的排列数（没有使用全部4种高度）
    int notAll4Heights = 0;
    for (int k = 1; k <= 3; ++k) {
        int sum = 0;
        for (int mask = 1; mask < (1 << 4); ++mask) {
            if (__builtin_popcount(mask) == k) {
                sum += pow(k, n);
            }
        }
        notAll4Heights += (k % 2 == 1 ? 1 : -1) * sum;
    }
    
    // 计算使用全部4种高度的排列数
    int all4Heights = pow(4, n) - notAll4Heights;
    
    // 计算使用全部4种高度且没有相邻差3的排列数
    vector<vector<vector<int> > > dp2(n + 1, vector<vector<int> >(1 << 4, vector<int>(5, 0)));
    for (int j = 1; j <= 4; ++j) {
        dp2[1][1 << (j - 1)][j] = 1;
    }
    for (int i = 1; i < n; ++i) {
        for (int mask = 0; mask < (1 << 4); ++mask) {
            for (int last = 1; last <= 4; ++last) {
                if (dp2[i][mask][last] == 0) continue;
                for (int next = 1; next <= 4; ++next) {
                    if (abs(last - next) != 3) {
                        int new_mask = mask | (1 << (next - 1));
                        dp2[i + 1][new_mask][next] += dp2[i][mask][last];
                    }
                }
            }
        }
    }
    int all4NoDiff3 = 0;
    for (int last = 1; last <= 4; ++last) {
        all4NoDiff3 += dp2[n][(1 << 4) - 1][last];
    }
    
    int result = all4Heights - all4NoDiff3;
    return result;
}

int main() {
    int n;
    while (cin >> n && n != -1) {
        cout << n << ": " << countValidLocks(n) << endl;
    }
    return 0;
}

代码说明

1. 数组定义

   • 定义三维数组 $s[18][5][4]$ 用于存储动态规划的中间状态。

2. dp 函数

   • 该函数用于进行动态规划递推，输入参数为 $x$，表示当前要计算的轮数。
   • 当 $x \geq 17$ 时，递归终止。
   • 根据递推公式计算 $s[x][i][j]$ 的值，然后递归调用 dp(x + 1) 计算下一轮的状态。

3. main 函数

   • 对 $n = 1$ 的情况进行初始化，根据 $i$ 的值设置 $s[1][i][j]$ 的初始值。
   • 调用 dp(2) 开始动态规划递推。
   • 使用 while 循环读取输入的正整数 $n$，当 $n$ 小于等于 $0$ 时退出循环。
   • 对于每个正整数 $n$，计算 $\sum_{i = 1}^{4}s[n][i][3]$ 的值并存储在 $ans$ 中，最后以 “n: 结果” 的格式输出结果。