您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 1055 【HAOI2008】玩具取名：DP + 記憶化搜索解析文法推導

編輯：關於C++

題目大意

初始符號為 {W, I, N, G} 中任一字母。每字母有若干產生式規則：可被替換為兩個字母（如 W -> II）。給定長字串 S（長度 ≤ 200），求：S 可能由哪些初始字母推導而來（按 WING 順序輸出）。若無解輸出 The name is wrong!。

規則數：W,I,N,G ≤ 16。

核心模型：上下文無關文法 (CFG) 識別問題

每條規則 X -> YZ 為二元產生式。問題等價於：給定 CFG（起始符號集 {W,I,N,G}，終結符號 {W,I,N,G}，產生式為輸入規則），判斷字串 S 是否可由各起始符號推導。此為經典CYK 演算法或區間 DP問題。

DP 狀態與轉移

dp[l][r][x]：區間 [l, r]（1-based）能否推導出符號 x（x=1..4 對應 W,I,N,G）。

基礎情況：l == r，dp[l][r][x] = (S[l] == char(x))。
遞歸情況：枚舉分割點 k (l ≤ k < r)，枚舉 x 的所有產生式 x -> yz。若 dp[l][k][y] && dp[k+1][r][z] 為真，則 dp[l][r][x] = true。

記憶化搜索實現遞歸，避免重複計算。狀態數 200*200*4 = 160,000，轉移枚舉分割點 O(len) 與產生式 O(16)，總複雜度 O(L^3 * R) ≈ 200^3 × 16 ≈ 1.28e8，邊界緊但可通過（實際剪枝後更快）。

完整程式碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

map<char, int> mp;
char ch[5] = {'*', 'W', 'I', 'N', 'G'};
char a[5][20][2], s[205];
int t[5], f[205][205][5];
bool flag;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x*10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int dp(int l, int r, int x) {
    if (f[l][r][x] != -1) return f[l][r][x];
    if (l == r) return f[l][r][x] = (mp[s[l]] == x);
    for (int i = 1; i <= t[x]; i++)
        for (int j = 1; j < r; j++)
            if (dp(l, j, mp[a[x][i][0]]) && dp(j+1, r, mp[a[x][i][1]]))
                return f[l][r][x] = 1;
    return f[l][r][x] = 0;
}

int main() {
    mp['W'] = 1; mp['I'] = 2; mp['N'] = 3; mp['G'] = 4;
    memset(f, -1, sizeof(f));
    for (int i = 1; i <= 4; i++) t[i] = read();
    for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= t[i]; j++)
            scanf("%s", a[i][j]);
    scanf("%s", s+1);
    int n = strlen(s+1);
    flag = false;
    for (int i = 1; i <= 4; i++)
        if (dp(1, n, i)) { flag = true; printf("%c", ch[i]); }
    if (!flag) printf("The name is wrong!\n");
    else printf("\n");
    return 0;
}