UVA 1626 括號序列修復：區間 DP 求最短合法超序列

問題描述

給定由 '(', ')', '[', ']' 組成的序列，插入最少字符使其成為合法括號序列。合法定義：空串合法；S 合法則 (S)、[S] 合法；A,B 合法則 AB 合法。輸出最短合法超序列（字典序最小？題目未要求，任意最短即可）。

區間 DP 狀態定義

• dp[l][r]：區間 [l,r] 變合法所需最少插入字符數
• 目標：dp[1][n]

轉移方程

dp[l][r] = min(
    dp[l+1][r-1]          if match(s[l], s[r]),
    dp[l][k] + dp[k+1][r] for k in [l, r-1]
)

邊界：dp[i][i]=1 (單字符需配對)，dp[l][r]=0 for l>r。

遞歸輸出方案

void print(int l, int r) {
    if (l > r) return;
    if (l == r) { putchar(s[l]=='('||s[l]==')'?"()":"[]"); return; }
    if (match(s[l],s[r]) && dp[l][r]==dp[l+1][r-1]) {
        putchar(s[l]); print(l+1,r-1); putchar(s[r]); return;
    }
    for (int k=l; k

關鍵細節

輸入可能含空行，需用 gets 讀取，scanf 會跳過空行導致對齊錯誤
多測試用例間輸出空行
match 函數判斷 '('-')' 或 '['-']'
長度 ≤100，O(n³) DP 完全可行


完整代碼
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int INF = 0x3f3f3f3f;
int dp[105][105]; char s[105]; int n;

bool match(char a,char b){ return (a=='('&&b==')')||(a=='['&&b==']'); }

void print(int l,int r){
    if(l>r) return;
    if(l==r){ printf(s[l]=='('||s[l]==')'?"()":"[]"); return; }
    if(match(s[l],s[r]) && dp[l][r]==dp[l+1][r-1]){
        putchar(s[l]); print(l+1,r-1); putchar(s[r]); return;
    }
    for(int k=l;k