2013
11-10

# 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: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
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
{
int l=0,max=-1,rr=-1;
{
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. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法