ABC 122 D We Like AGC

多次元DPの問題

dp[len][i][j][k] := 長さがlenのlen−２文字目が i len-1 文字目が j len 文字目が k である. 問題文に適する文字列の種類数 と定義する.

import java.util.Scanner;

class Main {
    static final long mod = 1000000007;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        /*
         * 0 a 1 c 2 g 3 t
         */
        long[][][][] dp = new long[n + 1][4][4][4];

        // 初期化処理を行う
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    if (i == 0 && j == 2 && k == 1)
                        continue;
                    if (i == 2 && j == 0 && k == 1)
                        continue;
                    if (i == 0 && j == 1 && k == 2)
                        continue;
                    dp[3][i][j][k] = 1;
                }
            }
        }
        // 後ろから分配していくdp
        for (int len = 1; len < n; len++) {
            // ijk => ijka => jka
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 4; k++) {
                        // 追加する文字
                        for (int a = 0; a < 4; a++) {
                            if (j == 0 && k == 2 && a == 1)
                                continue;
                            if (j == 0 && k == 1 && a == 2)
                                continue;
                            if (j == 2 && k == 0 && a == 1)
                                continue;
                            if (i == 0 && j == 2 && a == 1)
                                continue;
                            if (i == 0 && k == 2 && a == 1)
                                continue;
                            dp[len + 1][j][k][a] += dp[len][i][j][k];
                            dp[len + 1][j][k][a] %= mod;
                        }

                    }
                }
            }
        }

        // 最後に答えをだす
        int ans = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    ans += dp[n][i][j][k];
                    ans %= mod;
                }
            }
        }
        System.out.println(ans);

        sc.close();
    }
}