Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

从wr到re,大牛看看

Posted by xiaohaoshiyan at 2010-06-02 00:20:14 on Problem 1141
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator