UVA1626[Brackets sequence] 区间动态规划

题目链接

---

题意：用最小代价使不合法的括号序列合法。

---

解题报告：

合法的括号序列：

空序列合法

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("");  
    }  
}