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