首页 > 专题系列 > Java解POJ > POJ 2004 Mix and Build [解题报告] Java
2013
11-10

POJ 2004 Mix and Build [解题报告] Java

Mix and Build

问题描述 :

In this problem, you are given a list of words (sequence of lower case letters). From this list, find the longest chain of words w1, …, wn such that wi is a mixed extension of wi-1. A word A is a mixed extension of another word B if A can be formed by adding one letter to B and permuting the result. For example, “ab”, “bar”, “crab”, “cobra”, and “carbon” form a chain of length 5.

输入:

The input contains at least two, but no more than 10000 lines. Each line contains a word. The length of each word is at least 1 and no more than 20. All words in the input are distinct.

输出:

Write the longest chain that can be constructed from the given words. Output each word in the chain on a separate line, starting from the first one. If there are multiple longest chains, any longest chain is acceptable.

样例输入:

ab
arc
arco
bar
bran
carbon
carbons
cobra
crab
crayon
narc

样例输出:

ab
bar
crab
cobra
carbon
carbons

解题代码:

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
public class Main
{
 static my[] s=new my[10001];
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int l=0,max=-1,rr=-1;
  while(in.ready())
  {
	String t=in.readLine();
	s[l++]=new my(t);
  }
  Comparator< my> cp=new Comparator< my>()
  {
	public int compare(my o1, my o2) {
		return o1.l-o2.l;
	}
   };
   Arrays.sort(s,0,l,cp);
   for(int i=0;i< l;i++)
   {
	for(int j=0;j< i;j++)
	{
	 if(s[j].l==s[i].l) break;
	 if(s[j].l!=s[i].l-1) continue;
		int cnt=0,k=0;
		while(k< s[j].l&&cnt< 2)
		{
	          if(s[j].c[k]!=s[i].c[k+cnt]) cnt++;
		  else k++;
		}
		if(cnt< 2)
		{
		  if(s[i].n< s[j].n+1){
			s[i].n=s[j].n+1;
			s[i].r=j;
		  }		
		}	
	}
    }
	
   for(int i=0;i< l;i++)
   {
	if(s[i].n>max)
	{
		max=s[i].n;
		rr=i;
	}
   }
   p(rr);
 }

  static void p(int a)
  {
    if(s[a].r!=-1)
	p(s[a].r);
    System.out.println(s[a].s);
  }
}
class my
{
	String s;
	int n=0;
	int l;
	int r=-1;
	char[] c;
	public my(String t)
	{
		s=t;
		l=s.length();
		c=new char[l];
		for(int i=0;i< l;i++)
			c[i]=s.charAt(i);
		Arrays.sort(c);
	}
}

  1. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  2. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法