pku2138 Travel Games DP找最长链

题意是这样
给出一些字符串，如果字符串i可以由字符串j删除一个字母而获得，则字符串i可以导出字符串j。
现求以固定字符串开头的最长链
把字符串看成图的节点，一次DP即可~
预处理的时候有点技巧，先对字符串按其长度排序，然后线扫+Hash即可在线性时间内构图，总复杂度即排序的复杂度nlogn
现在对java是又恨又爱，喜欢里面的Hash表，但是经常暴内存空间让人很头疼，经常是不调用System.gc就MLE，每组测试数据前调用一次就TLE，然后就开始艰难的尝试，2组测试数据调用一次，3组测试数据调用一次，无限循环
 1import java.io.*;
 2import java.util.*;
 3public class Main {
 4
 5    /**
 6     * @param args
 7     */
 8    static class cmp implements Comparator<String>
 9    {
10        public int compare(String a,String b)
11        {
12            return a.length()-b.length();
13        }
14    }
15    static ArrayList<String> data=new ArrayList<String>();
16    static HashMap<String,Integer> refer=new HashMap<String,Integer>();
17    static ArrayList<Integer> g[];
18    static int dp[];
19    static int path[];
20    static int solve(int pos)
21    {
22        if(dp[pos]!=-1) return dp[pos];
23        else
24        {
25            dp[pos]=1;
26            for(int p:g[pos])
27                if(solve(p)+1>dp[pos])
28                {
29                    dp[pos]=solve(p)+1;
30                    path[pos]=p;
31                }
32            return dp[pos];
33        }
34    }
35    public static void main(String[] args) throws IOException{
36        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
37        in.nextToken();
38        int num=(int)in.nval;
39        in.nextToken();
40        String str=in.sval;
41        int startnum=-1;
42        g=new ArrayList[num];
43        dp=new int[num];
44        path=new int[num];
45        Arrays.fill(dp,-1);
46        Arrays.fill(path,-1);
47        for(int i=1;i<=num;i++)
48        {
49            in.nextToken();
50            data.add(in.sval);
51        }
52        Collections.sort(data,new cmp());
53        for(int i=0;i<data.size();i++)
54        {
55            g[i]=new ArrayList<Integer>();
56            for(int j=0;j<data.get(i).length();j++)
57              if(refer.containsKey(data.get(i).substring(0,j)+data.get(i).substring(j+1)))
58                  g[refer.get(data.get(i).substring(0,j)+data.get(i).substring(j+1))].add(i);
59            refer.put(data.get(i), i);
60            if(startnum==-1&&str.equals(data.get(i))) startnum=i;
61        }
62        solve(startnum);
63        while(path[startnum]!=-1) startnum=path[startnum];
64        System.out.println(data.get(startnum));
65    }
66
67}
68
69

posted on 2010-11-01 22:21 yzhw 阅读(205) 评论(0)  编辑 收藏 引用 所属分类: DP 、graph


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年11月>
日一二三四五六
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜