UVA 1626 / ZOJ 1463 括号序列：区间 DP 构造最短合法超序列

题目大意

给定由 ()[] 组成的字符串（长 ≤ 100），求最短的合法括号序列，使其包含原串为子序列。合法定义：空串、括号包裹合法串、合法串拼接。

区间 DP 状态定义

dp[l][r]：区间 [l,r] 构造最短合法超序列的长度。

转移方程

1. 若 s[l] 与 s[r] 匹配：dp[l][r] = min(dp[l][r], dp[l+1][r-1] + 2)
2. 分割区间：dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r]) for k∈[l,r-1]

初始：dp[i][i]=1（单字符需补一对），dp[i][j]=0 (i>j)。

路径重构

递归 PRINT(l,r)：

• 若 l==r：输出匹配对 () 或 []
• 若 l>r：返回
• 若最优来自匹配：输出 s[l]，递归 (l+1,r-1)，输出 s[r]
• 否则按最优分割点 k 递归 (l,k) 和 (k+1,r)

C++ 完整实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;

const int MAXN = 300;
const int INF = 0x3f3f3f3f;
char str[MAXN];
int n, dp[MAXN][MAXN];

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

void PRINT(int l, int r) {
    if (l == r) {
        if (str[l]=='(' || str[l]==')') putchar('('), putchar(')');
        else putchar('['), putchar(']');
        return;
    }
    if (l > r) return;
    int pos = -1, best = INF;
    if (match(l, r)) best = dp[l+1][r-1];
    for (int k = l; k+1 <= r; ++k)
        if (dp[l][k] + dp[k+1][r] < best) {
            best = dp[l][k] + dp[k+1][r];
            pos = k;
        }
    if (pos == -1) {
        putchar(str[l]);
        PRINT(l+1, r-1);
        putchar(str[r]);
    } else {
        PRINT(l, pos);
        PRINT(pos+1, r);
    }
}

int main() {
    int T; scanf("%d", &T); getchar();
    while (T--) {
        gets(str); memset(str, 0, sizeof(str)); gets(str); // 读取空行+数据行
        n = strlen(str);
        if (n == 0) { putchar('\n'); continue; }
        memset(dp, 0x3f, sizeof(dp));
        for (int i = 0; i < n; ++i) dp[i][i] = 1;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (i > j) dp[i][j] = 0;
        for (int len = 2; len <= n; ++len)
            for (int i = 0; i+len-1 < n; ++i) {
                int j = i+len-1;
                if (match(i, j)) dp[i][j] = min(dp[i][j], dp[i+1][j-1]);
                for (int k = i; k+1 <= j; ++k)
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        PRINT(0, n-1);
        putchar('\n');
    }
    return 0;
}

复杂度

• 时间：O(n³) = 10⁶，n≤100 瞬间通过
• 空间：O(n²)

关键技巧

1. 空串处理：输入含空行，需 gets 两次跳过
2. 输出格式：测试用例间空行，flag++ 控制
3. 匹配判断：仅 () 和 [] 互配