题解 | 暗黑的字符串

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

class Solution {
public:
    long long countDarkStrings(int n) {
        // 如果长度小于3，直接计算
        if (n <= 0) return 0;
        if (n == 1) return 3;
        if (n == 2) return 9;
        
        // dp[i][state]表示长度为i，最后三个字符状态为state的字符串数量
        vector<vector<long long>> dp(n + 1, vector<long long>(27, 0));
        
        // 初始化长度为1的情况
        dp[1][0] = 3;  // A=0, B=1, C=2
        
        // 初始化长度为2的情况
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                dp[2][i * 3 + j]++;
            }
        }
        
        // 动态规划
        for (int i = 3; i <= n; i++) {
            for (int last = 0; last < 27; last++) {
                int x = last / 9;      // 倒数第三个字符
                int y = (last / 3) % 3;// 倒数第二个字符
                int z = last % 3;      // 倒数第一个字符
                
                for (int next = 0; next < 3; next++) {
                    // 检查新的三个字符是否包含ABC
                    if (!containsABC(y, z, next)) {
                        int newState = (y * 3 + z) * 3 + next;
                        dp[i][newState] += dp[i-1][last];
                    }
                }
            }
        }
        
        // 统计所有暗黑字符串
        long long result = 0;
        for (int state = 0; state < 27; state++) {
            result += dp[n][state];
        }
        
        return result;
    }
    
private:
    // 检查三个字符是否包含ABC
    bool containsABC(int a, int b, int c) {
        vector<bool> has(3, false);
        has[a] = has[b] = has[c] = true;
        return has[0] && has[1] && has[2];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    while (cin >> n) {
        Solution sol;
        cout << sol.countDarkStrings(n) << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public long countDarkStrings(int n) {
            if (n <= 0) return 0;
            if (n == 1) return 3;
            if (n == 2) return 9;
            
            long[][] dp = new long[n + 1][27];
            
            // 初始化
            dp[1][0] = 3;
            
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    dp[2][i * 3 + j]++;
                }
            }
            
            // 动态规划
            for (int i = 3; i <= n; i++) {
                for (int last = 0; last < 27; last++) {
                    int x = last / 9;
                    int y = (last / 3) % 3;
                    int z = last % 3;
                    
                    for (int next = 0; next < 3; next++) {
                        if (!containsABC(y, z, next)) {
                            int newState = (y * 3 + z) * 3 + next;
                            dp[i][newState] += dp[i-1][last];
                        }
                    }
                }
            }
            
            long result = 0;
            for (int state = 0; state < 27; state++) {
                result += dp[n][state];
            }
            
            return result;
        }
        
        private boolean containsABC(int a, int b, int c) {
            boolean[] has = new boolean[3];
            has[a] = has[b] = has[c] = true;
            return has[0] && has[1] && has[2];
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            Solution sol = new Solution();
            System.out.println(sol.countDarkStrings(n));
        }
        sc.close();
    }
}

class Solution:
    def count_dark_strings(self, n: int) -> int:
        if n <= 0:
            return 0
        if n == 1:
            return 3
        if n == 2:
            return 9
            
        # dp[i][state]表示长度为i，最后三个字符状态为state的字符串数量
        dp = [[0] * 27 for _ in range(n + 1)]
        
        # 初始化
        dp[1][0] = 3
        
        for i in range(3):
            for j in range(3):
                dp[2][i * 3 + j] += 1
        
        # 动态规划
        for i in range(3, n + 1):
            for last in range(27):
                x = last // 9          # 倒数第三个字符
                y = (last // 3) % 3    # 倒数第二个字符
                z = last % 3           # 倒数第一个字符
                
                for next_char in range(3):
                    # 检查新的三个字符是否包含ABC
                    if not self.contains_abc(y, z, next_char):
                        new_state = (y * 3 + z) * 3 + next_char
                        dp[i][new_state] += dp[i-1][last]
        
        return sum(dp[n])
    
    def contains_abc(self, a: int, b: int, c: int) -> bool:
        has = [False] * 3
        has[a] = has[b] = has[c] = True
        return all(has)

def main():
    while True:
        try:
            n = int(input())
            sol = Solution()
            print(sol.count_dark_strings(n))
        except EOFError:
            break

if __name__ == "__main__":
    main()