| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
从wr到re,大牛看看import java.io.*;
import java.util.*;
class Main
{
static Scanner in;
static PrintWriter out;
static int[][] data=new int[200][200];//最优加入括号个数
static String[][] da=new String[200][200];//最优结果
public static void main(String[] args)
{
in=new Scanner(new InputStreamReader(System.in));
out=new PrintWriter(new OutputStreamWriter(System.out));
String str=in.nextLine();
if (str.charAt(str.length()-1)==' ')
{
out.println();
}
else
{
int L=str.length();
for (int i=0;i<L ;i++ )
{
for (int j=i;j<L ;j++ )
{
data[i][j]=1000;
da[i][j]="";
}
}
for (int i=L-1;i>=0 ;i-- )
{
for (int j=i;j<L ;j++ )
{
if (i==j)
{
if (str.charAt(i)=='('||str.charAt(j)==')')
{
da[i][j]="()";
data[i][j]=1;
}
if (str.charAt(i)=='['||str.charAt(j)==']')
{
da[i][j]="[]";
data[i][j]=1;
}
}
else
{
if (str.charAt(i)=='('&&str.charAt(j)==')')
{
if (data[i][j]>data[i+1][j-1])
{
if ((i+1)<=(j-1))
{
da[i][j]="("+da[i+1][j-1]+")";
data[i][j]=data[i+1][j-1];
}
else
{
da[i][j]="()";
data[i][j]=data[i+1][j-1];
}
}
}
if (str.charAt(i)=='['&&str.charAt(j)==']')
{
if (data[i][j]>data[i+1][j-1])
{
if ((i+1)<=(j-1))
{
da[i][j]="["+da[i+1][j-1]+"]";
data[i][j]=data[i+1][j-1];
}
else
{
da[i][j]="[]";
data[i][j]=data[i+1][j-1];
}
}
}
for (int n=i;n<j ;n++ )
{
if (data[i][n]+data[n+1][j]<=data[i][j])
{
data[i][j]=data[i][n]+data[n+1][j];
da[i][j]=da[i][n]+da[n+1][j];
//out.println((i)+" "+(j)+(da[i][j]));
}
}
}
}
}
//out.println(L);
//out.println(str);
out.println(da[0][L-1]);
//out.println(da[0][L-1].length());
}
out.close();
in.close();
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator