作者在 2008-06-04 22:32:07 发布以下内容
使用的dp,主要的难度来自于对串的储存,很经典的dp,可以参看黑素115夜
感谢stl,还是很方便的东西
#include <iostream>
#include <string>
using namespace std;
string ans[110][110];
string s;
int d[110][110]={0};
bool index[110][110]={0};
int bb(int f,int e)
{
if(index[f][e])
return d[f][e];
#include <string>
using namespace std;
string ans[110][110];
string s;
int d[110][110]={0};
bool index[110][110]={0};
int bb(int f,int e)
{
if(index[f][e])
return d[f][e];
else if(f>e) {return 0;}
else if (f==e)
{
if (s[f] == '(') ans[f][e] = "()";
if (s[f] == ')') ans[f][e] = "()";
if (s[f] == '[') ans[f][e] = "[]";
if (s[f] == ']') ans[f][e] = "[]";
return 1;
else if (f==e)
{
if (s[f] == '(') ans[f][e] = "()";
if (s[f] == ')') ans[f][e] = "()";
if (s[f] == '[') ans[f][e] = "[]";
if (s[f] == ']') ans[f][e] = "[]";
return 1;
}
else
{
int aans=0xfffffff;
if(s[f]=='('&&s[e]==')')
{
if(bb(f+1,e-1)<aans)
{
aans=bb(f+1,e-1);
ans[f][e]='('+ans[f+1][e-1]+')';
}
}
else if(s[f]=='['&&s[e]==']')
{
if(bb(f+1,f-1)<aans)
{
aans=bb(f+1,e-1);
ans[f][e]='['+ans[f+1][e-1]+']';
}
}
/* else if(s[f]=='[')
{
if(bb(f+1,e)+1<aans)
{
aans=bb(f+1,e)+1;
ans[f][e]=ans[f+1][e]+']';
}
}
else if(s[f]=='(')
{
if(bb(f+1,e)+1<aans)
{
aans=bb(f+1,e)+1;
ans[f][e]=ans[f+1][e]+')';
}
}
else if(s[e]==')')
{
if(bb(f,e-1)+1<aans)
{
aans=bb(f,e-1)+1;
ans[f][e]='('+ans[f][e-1];
}
}
else if(s[e]==']')
{
if(bb(f,e-1)+1<aans)
{
aans=bb(f,e-1)+1;
ans[f][e]='['+ans[f][e-1];
}
}
*/
for(int i=f;i<e;i++)
if(aans>bb(f,i)+bb(i+1,e))
{
aans=bb(f,i)+bb(i+1,e);
ans[f][e]=ans[f][i]+ans[i+1][e];
}
d[f][e]=aans;
index[f][e]=true;
return aans;
{
int aans=0xfffffff;
if(s[f]=='('&&s[e]==')')
{
if(bb(f+1,e-1)<aans)
{
aans=bb(f+1,e-1);
ans[f][e]='('+ans[f+1][e-1]+')';
}
}
else if(s[f]=='['&&s[e]==']')
{
if(bb(f+1,f-1)<aans)
{
aans=bb(f+1,e-1);
ans[f][e]='['+ans[f+1][e-1]+']';
}
}
/* else if(s[f]=='[')
{
if(bb(f+1,e)+1<aans)
{
aans=bb(f+1,e)+1;
ans[f][e]=ans[f+1][e]+']';
}
}
else if(s[f]=='(')
{
if(bb(f+1,e)+1<aans)
{
aans=bb(f+1,e)+1;
ans[f][e]=ans[f+1][e]+')';
}
}
else if(s[e]==')')
{
if(bb(f,e-1)+1<aans)
{
aans=bb(f,e-1)+1;
ans[f][e]='('+ans[f][e-1];
}
}
else if(s[e]==']')
{
if(bb(f,e-1)+1<aans)
{
aans=bb(f,e-1)+1;
ans[f][e]='['+ans[f][e-1];
}
}
*/
for(int i=f;i<e;i++)
if(aans>bb(f,i)+bb(i+1,e))
{
aans=bb(f,i)+bb(i+1,e);
ans[f][e]=ans[f][i]+ans[i+1][e];
}
d[f][e]=aans;
index[f][e]=true;
return aans;
}
}
int main()
{
cin >>s;
if(s.empty())
{
cout<<endl;
return 0;
}
int b;
b=bb(0,s.size()-1);
cout<<ans[0][s.size()-1]<<endl;
return 0;
}
int main()
{
cin >>s;
if(s.empty())
{
cout<<endl;
return 0;
}
int b;
b=bb(0,s.size()-1);
cout<<ans[0][s.size()-1]<<endl;
return 0;
}