uva-1626 Brackets sequence 区间dp

给一个只含有()[]的序列添加最少的符号使括号成为正规序列

如果s可以分成[s']或(s')则转移到s'状态，然后对于区间[j, l]将区间分成两部分, dp[j][l] = min(dp[j][l], dp[j][k] + dp[k + 1][l]), j < k < l;

在处理过程中用c[i][j]记录区间[i, j]最优的分割点， 如果值为-1表示按第一种方式转移最佳，借助c数组递归输出最优解。

#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
int dp[110][110], c[110][110];
char s[110];
void dfs(int b, int e) {
    if(b > e)
        return;
    if(b == e) {
        if(s[b] == '(' || s[b] == ')')
            printf("()");
        else printf("[]");
    }
    else if(c[b][e] == -1) {
        printf("%c", s[b]);
        dfs(b + 1, e - 1);
        printf("%c", s[e]);
    }
    else {
        dfs(b, c[b][e]);
        dfs(c[b][e] + 1, e);
    }
}
int main() {
    int t, n, i, j, k;
    scanf("%d%*c", &t);
    while(t--) {
        getchar();
        gets(s);
        n = strlen(s);
        memset(dp, 0, sizeof(dp));
        memset(c, -1, sizeof(c));
        for(i = 0; i < n; i++)
            dp[i][i] = 1;
        for(i = 1; i < n; i++) {
            for(j = 0; j < n - i; j++) {
                int l = j + i;
                if((s[j] == '(' && s[l] == ')') || (s[j] == '[' && s[l] == ']'))
                    dp[j][l] = dp[j + 1][l - 1];
                else dp[j][l] = INF;
                for(k = j; k < l; k++) {
                    if(dp[j][l] > dp[j][k] + dp[k + 1][l]) {
                        dp[j][l] = dp[j][k] + dp[k + 1][l];
                        c[j][l] = k;
                    }
                }
            }
        }
        dfs(0, n - 1);
        printf("\n");
        if(t) printf("\n");
    }
    return 0;
}