题目意思就是输入一串括号，让你找到最小的补偿数目使括号串合法，并且输出补全后的串。
基本是区间DP的模板题，该题特别让你输出补全后的答案。这和区间dp的反向思路很像，就是把一个大的区间划分为多个互不干扰的区间来输出。划分到需要补充的点时，就直接补充。
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
int n,k,s,dp[][];
char a[];
const long long LNF = 0x3f3f3f3f3f3f;
bool pd(int i,int j)//判断a[i]和a[j]是否为一对括号
{
if(a[i]=='('&&a[j]==')') return true;
if(a[i]=='['&&a[j]==']') return true;
return false;
}
void pr(int i,int j)//输出区间[i,j]的补全版本
{
if(i>j) return;
if(i==j) //递归到了一个点上时，直接输出补全后的一对括号
{
if(a[i]=='('||a[i]==')') printf("()");
else printf("[]");
return;
}
int m=dp[i][j];
if(pd(i,j)&&m==dp[i+][j-]) //如果成立，意味着a[i]和a[j]是一对匹配的括号
{
printf("%c",a[i]);
pr(i+,j-);
printf("%c",a[j]);
return;
}
for(int k=i;k<j;k++)
{
if(m==dp[i][k]+dp[k+][j])
{
pr(i,k);
pr(k+,j);
return ;//满足条件就代表找到了一个分割点，可以划分成两个独立区间的输出。
}
}
}
int main()
{
while(gets(a))
{
int n=strlen(a);
memset(dp,LNF,sizeof(dp));
for(int i=;i<n;i++) dp[i][i]=,dp[i+][i]=; //单个符号需要补一个括号才能补全 无符号则本身就合法
for(int i=n-;i>=;i--) //从后往前更新，保证每次遍历只修改之前的状态一次
for(int j=i+;j<=n-;j++)
{
dp[i][j]=LNF;
if(pd(i,j)) dp[i][j]=dp[i+][j-];
for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);
// cout<<dp[i][j]<<endl;
}
pr(,n-);
printf("\n"); }
}