Submission #1151951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151951		goodspeed0208	Misspelling (JOI22_misspelling)	C++20	0 / 100	0 ms	324 KiB

misspelling

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

const int MAX_N = 205;
const int ALPHABET = 26;
const int INF = 1e9+7;

// dp[pos][x][c][op] -> 記錄以 c 結尾的字串數
long long dp[MAX_N][MAX_N][ALPHABET][2];  // 0: '<', 1: '>'

int N, M;
vector<pair<int, int>> constraints;  // (i, j) 條件: T[i] <= T[j]

void solve() {
    cin >> N >> M;
    constraints.resize(M);
    for (auto &[i, j] : constraints) {
        cin >> i >> j;
        i--, j--;  // 轉換為 0-based
    }

    // 初始化 dp，只有長度為 1 的字串是合法的
    for (int c = 0; c < ALPHABET; c++) {
        dp[N-1][N-1][c][0] = 1;
        dp[N-1][N-1][c][1] = 1;
    }

    // 自底向上填表
    for (int pos = N - 2; pos >= 0; pos--) {
        for (int x = pos; x < N; x++) {
            for (int c = 0; c < ALPHABET; c++) {
                for (int op = 0; op < 2; op++) {
                    long long &cur = dp[pos][x][c][op];

                    // 保持相同字符，繼承之前的 dp
                    cur += dp[pos + 1][x][c][op];

                    // 選擇不同字符，更新 x
                    for (int c2 = 0; c2 < ALPHABET; c2++) {
                        if (c2 == c) continue;
                        if ((c2 < c && op == 0) || (c2 > c && op == 1)) {
                            cur += dp[pos + 1][pos][c2][op];
                        }
                    }
                    cur %= INF;
                }
            }
        }
    }

    // 檢查 constraints，將不滿足條件的狀態設為 0
    for (auto &[i, j] : constraints) {
        for (int c1 = 0; c1 < ALPHABET; c1++) {
            for (int c2 = 0; c2 < ALPHABET; c2++) {
                if (c1 > c2) {  // 違反 T[i] <= T[j]
                    dp[i][j][c1][1] = 0;
                }
            }
        }
    }

    // 統計結果
    long long result = 0;
    for (int c = 0; c < ALPHABET; c++) {
        for (int op = 0; op < 2; op++) {
            result += dp[0][0][c][op];
            result %= INF;
        }
    }
    
    cout << result << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 20
• Subtask 3: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11