http://acm.pku.edu.cn/JudgeOnline/problem?id=1141
動態(tài)規(guī)劃的一題 ，用三維數(shù)組保存中間狀態(tài)；
?keeping studying......
//a數(shù)組動態(tài)記錄串中不符合規(guī)則的符號個數(shù)
//?R[i][j]數(shù)組動態(tài)記錄from?i?dao?j加上最少的符號個數(shù)后變成的串?
#include?<iostream>
#include?<string>
using?namespace?std;
int?a[101][101];
char?record[101];
string?R[100][101];
int?KHao(char?p[],?int?n)
{
????int?i,?j,?k,?t;
????for(i?=?0;?i?<?n;?i++)
????????record[i]?=?0;
??????//初始化；?
????for(i?=?1;?i?<?n;?i++){
??????????a[i][i?-?1]??=?0;
??????????R[i][i?-?1]?=?"";
??????????}
????for(i?=?0;?i?<?n;?i++)a[i][i]?=?1;
????for(t?=?1;?t?<?n;?t++)
????{
????????for(i?=?0;?i?<?n?-?t;?i++)
????????{????j?=?i?+?t;
????????????a[i][j]?=?1000;
????????????if(p[i]?==?'('&&p[j]?==?')'||p[i]?==?'['&&p[j]?==?']')
????????????{
????????????????if(a[i][j]?>?a[i?+?1][j?-?1])
????????????????{
????????????????????a[i][j]?=?a[i?+?1][j?-?1];
????????????????????R[i][j]?=?p[i]?+?R[i?+?1][j?-?1]?+?p[j];
????????????????}
????????????}
????????????if(p[i]?==?'('||p[i]?==?'[')
???????????{
????????????????if(a[i][j]?>?a[i?+?1][j]?+?1)
????????????????{
????????????????????a[i][j]?=?a[i?+?1][j]?+?1;
????????????????????if(p[i]?==?'(')
???????????????????????R[i][j]?=?"("?+?R[i?+?1][j]?+?")";
????????????????????if(p[i]?==?'[')
????????????????????{
???????????????????????R[i][j]?=?"["?+?R[i?+?1][j]?+?"]";
????????????????????}
????????????????}
//????????????????cout?<<?i?<<?"?"?<<?j?<<?"?"?<<?R[i?+?1][j]?<<?endl;

???????????}
???????????if(p[j]?==?')'||p[j]?==?']')
???????????{??
???????????????if(a[i][j]?>?a[i][j?-?1]?+1)
???????????????{
???????????????????a[i][j]?=?a[i][j?-?1]?+?1;
???????????????????if(p[j]?==?')')
???????????????????{
???????????????????????R[i][j]?=?"("?+?R[i][j?-?1]?+?")";
???????????????????}
???????????????????if(p[j]?==?']')
???????????????????{
???????????????????????R[i][j]?=?"["?+?R[i][j?-?1]?+?"]";
???????????????????}???????
???????????????}
???????????}???????????????
???????????for(k?=?i;?k?<?j;?k++)
???????????{
????????????????if(a[i][j]?>?a[i][k]?+?a[k?+?1][j])
????????????????{
????????????????????a[i][j]?=?a[i][k]?+?a[k?+?1][j];
????????????????????R[i][j]?=?R[i][k]?+?R[k?+?1][j];
????????????????}
???????????}
?????//???????cout?<<?i?<<?"?"?<<?j?<<?"?"?<<?a[i][j]?<<?endl;
????????}
????????
????}
????cout?<<?R[0][n?-?1]?<<?endl;
????return?n?-?a[0][n?-?1];
????
}
int?main()
{
????int?p_l;
????int?result;
????char?p[101];
????int?i,?j,?t;
????while(cin?>>?p)
????{
????????if(p[0]?==?'e')break;
????????p_l?=?strlen(p);
????????for(i?=?0;?i?<?p_l;?i++)
????????{
??????????????//初始化；?
????????????if(p[i]?==?'('||p[i]?==?')')
????????????????R[i][i]?=?"()";
????????????if(p[i]?==?'['||p[i]?==?']')
????????????????R[i][i]?=?"[]";
????????}
????????KHao(p,?p_l);
????}
????return?0;
}