题目链接
题意：用最小代价使不合法的括号序列合法。
解题报告：
合法的括号序列：
空序列合法
S合法 那么 （S）或 [S] 合法
A 合法， B 合法， 那么 AB 合法
我们定义 d[i][j] 为 把 原始序列 S中 S[i]~S[j] 变为合法序列 的最小代价
那么有三种情况：
单独的一个括号 d[i][i]=1
找到 括号 S[i] 和 S[j] 匹配 dp[i][j]=min(dp[i][j], dp[i+1][j-1])
把序列分割为两份，分别找代价，再合并 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]) i<=k < j
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char S[105];
int d[105][105], n;int match(char a, char b){return (a=='('&&b==')')||(a=='['&&b==']');
}
void dp(){for ( int i=0; i<n; i++ ) d[i][i]=1, d[i+1][i]=0;for ( int i=n-2; i>=0; i--)for ( int j=i+1; j<n; j++ ){d[i][j]=n;if( match(S[i],S[j]) ) d[i][j]=min(d[i][j],d[i+1][j-1]);for ( int k=i; k<j; k++ ) d[i][j]=min(d[i][j], d[i][k]+d[k+1][j]);}
} void put(int i, int j){if( i>j ) return;if( i==j ){if( S[i]=='(' || S[i]==')' ) printf("()");else printf("[]");return ;}int ans=d[i][j];if( match(S[i], S[j]) && ans==d[i+1][j-1] ){printf("%c", S[i] ); put(i+1,j-1); printf("%c", S[j] );return ;}for ( int k=i; k<j; k++ ) if( ans==d[i][k]+d[k+1][j] ){put(i,k), put(k+1,j);return ;} }
int main(){int T;scanf("%d", &T);getchar(); while (T--) { gets(S); gets(S); n=strlen(S); dp(); put(0,n-1); puts(""); if (T) puts(""); }
}