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

我这样想是不是正确的想法。。。。。??(文字描述我的问题,请大牛们帮忙)

Posted by faen at 2005-05-25 14:41:21 on Problem 2004
想法就是用动态规划来做,中间结果用一个哈希表存储(HashMap<String,Int>)。
我想可能差不多, 提交后wa,  可是我测试了好多组数据(包括自己构造的,结果都正确)。
怎么回事呢,劳驾各位。或者给我些易错的测试数据把
import java.util.*;
import java.io.*;
public class Main
{
	public static void main(String [] args)throws Exception
	{

		Scanner cin=new Scanner(System.in);
		ArrayList[] asp=new ArrayList[21];
		HashMap hmsi=new HashMap();
		HashMap hmss=new HashMap();
		for(int i=0;i<21;i++)
			asp[i]=new ArrayList();
		
		int rmax=0;
		String smax="";
		while(cin.hasNext())
		{
			String s=cin.next();
			int length=s.length();
			asp[length].add(s);
			if(length==1)
			{
				hmsi.put(s,Integer.valueOf(1));
				hmss.put(s,s);
				rmax=1;
				smax=s;
			}
		}
		
		for(int i=2;i<21;i++)
		{
			if(asp[i].size()>0)
			{
				if(asp[i-1].size()==0)
				{
					for(int j=0;j<asp[i].size();j++)
					{
						hmsi.put(asp[i].get(j),Integer.valueOf(1));
						hmss.put(asp[i].get(j),asp[i].get(j));
						if(1>rmax)
						{
							rmax=1;
							smax=(String)asp[i].get(j);
						}
					}
				}
				else
				{
					for(int j=0;j<asp[i].size();j++)
					{
						int tmax=0;
						String ts="$$";
						for(int k=0;k<asp[i-1].size();k++)
						{
							if(isOk(asp[i].get(j),asp[i-1].get(k))&&tmax<((Integer)hmsi.get(asp[i-1].get(k))).intValue())
							{
								tmax=((Integer)hmsi.get(asp[i-1].get(k))).intValue();
								ts=(String)asp[i-1].get(k);
							}
							
						}
						if(tmax+1>rmax)
						{
							rmax=tmax+1;
							smax=(String)asp[i].get(j);
						}
						hmsi.put(asp[i].get(j),tmax+1);
						if(hmss.containsKey(ts))
							hmss.put(asp[i].get(j),(String)hmss.get(ts)+"#"+(String)asp[i].get(j));
						else
							hmss.put(asp[i].get(j),(String)asp[i].get(j));
					}
				}
				
			}
		}
	//	System.out.println(hmss);
		String rrs=(String)hmss.get(smax);
		rrs=rrs.replaceAll("^null","");
		String [] rras=rrs.split("#");
		for(int i=0;i<rras.length;i++)
		{
			if(rras[i].equals(""))
				continue;
			System.out.println(rras[i]);
		}
	}
	private static boolean isOk(Object obig,Object osmall)
	{
		String big=(String)obig;
		String small=(String)osmall;
		for(int i=0;i<small.length();i++)
		{
			char c=small.charAt(i);
			if(big.indexOf(c+"")<0)
				return false;
		}
		return true;
	}
	
}


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