poj1141题解
题意
空序列是规则序列；用小括号(或者方括号)把一个规则序列括起来依然是规则序列；两个规则序列并列在一起仍然是规则序列。
给出一个括号字符串S，求一个规则序列ANS，满足S是ANS的子序列且ans尽可能短。
ANS不唯一，是special judge
记录状态转移过程的dp+递归输出
先把问题变简单一点，
①只求最少需要添加多少个字符f[l][i]表示处理从s[i]开始的l个字符需要添加的最少字符
显然
f[0][i]=0
f[1][i]=1
f[l][i] ------- s[i]...s[i+l-1]
可以拆分成AB两段来解决，枚举拆分的第一段的长度ll
ll从1到l-1
显然需要添加字符数=f[ll][i]+f[l-ll][i+ll]
f[l][i]只要取这些不同ll取法下的最小值即可
注意若s[i]与s[i+l-1]已经匹配，则可以变成(A)或[A]的模式，即可以转换成f[l-2][i+1]的问题；
ps，这里wa了一次，一开始s[i]与s[i+l-1]匹配时没有枚举ll拆分。
②如何构造出添加后的最短字符串？只需要另开一个数组在上面f[i][j]选取最优的ll时记录下ll，那么就可以成功的缩小问题的规模。当然有可能是情况(1)，这种可以特殊记录，比如记录取的ll是0.
规模可以一步步的缩小，然后终止条件——
规模足够小时——
（1）只有一个字符时，显然只需要在它右边添加对应的右括号即可
（2）只有0个字符时，什么都不干，不再缩小
#include<cstdio>
#include<cstring>
using namespace std;
const int maxl=1000;
char ss[maxl+1],s[maxl+1];
int f[maxl+1][maxl],prel[maxl+1][maxl];
inline char l2r(char a)
{
return a=='('?')':(a=='['?']':0);
}
void print(int l,int i)
{
if (l==0) return;
else if (l==1) {
switch(s[i]){
case '(':
case ')':printf("()");return;
case '[':
case ']':printf("[]");return;
}
} else if (!prel[l][i]) {
printf("%c",s[i]);
print(l-2,i+1);
printf("%c",s[i+l-1]);
} else {
print(prel[l][i],i);
print(l-prel[l][i],i+prel[l][i]);
}
}
int main()
{
int len,t,ll;
while(gets(ss)!=NULL) {
len=0;
for (int i=0;ss[i];++i)
if (ss[i]=='('||ss[i]==')'||ss[i]=='['||ss[i]==']')
s[len++]=ss[i];
for (int i=0;i<len;++i) {
f[0][i]=0;f[1][i]=1;
}
for (int l=2;l<=len;++l)
for (int i=0;i+l<=len;++i) {
f[l][i]=l+1;
for (ll=1;ll<l;++ll) {
t=f[ll][i]+f[l-ll][i+ll];
if(f[l][i]>t) {
f[l][i]=t;
prel[l][i]=ll;
}
}
if (l2r(s[i])==s[i+l-1]) {
t=f[l-2][i+1];
if(f[l][i]>t) {
f[l][i]=t;
prel[l][i]=0;
}
}
}
print(len,0);
printf("\n");
}
return 0;
}
