青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

pku2138 Travel Games DP找最長鏈

題意是這樣
給出一些字符串，如果字符串i可以由字符串j刪除一個字母而獲得，則字符串i可以導出字符串j。
現求以固定字符串開頭的最長鏈
把字符串看成圖的節(jié)點，一次DP即可~
預處理的時候有點技巧，先對字符串按其長度排序，然后線掃+Hash即可在線性時間內構圖，總復雜度即排序的復雜度nlogn
現在對java是又恨又愛，喜歡里面的Hash表，但是經常暴內存空間讓人很頭疼，經常是不調用System.gc就MLE，每組測試數據前調用一次就TLE，然后就開始艱難的嘗試，2組測試數據調用一次，3組測試數據調用一次，無限循環(huán)

 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 閱讀(241) 評論(0)  編輯 收藏 引用 所屬分類: DP 、graph

只有注冊用戶登錄后才能發(fā)表評論。

【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關文章: pku3903 最長遞增字串的單調性優(yōu)化 pku 3998 Land Division DP斜率優(yōu)化 The 36th ACM/ICPC Asia Regional Dalian Online Contest 大連2011ICPC網絡賽 個人題解 pku3124 The Bookcase 擴展背包好題 pku1202 Family DAG圖上的概率DP pku 1946 Cow Cycling 非常好的DP pku1948 Triangular Pastures DP+枚舉。海倫公式 pku1335 Digital Onion 遞歸 pku1332 Finding Liars DP 經典好題 pku1337 A Lazy Worker 很詭異的DP

網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理

Powered by:
C++博客
Copyright © yzhw

導航

• 首頁
• 新隨筆
• 聯系
• 管理

統(tǒng)計

• 隨筆 - 183
• 文章 - 2
• 評論 - 27
• 引用 - 0

公告

留言簿(1)

• 給我留言
• 查看公開留言
• 查看私人留言

隨筆分類(227)

• combination math(7) (rss)
• data struct(48) (rss)
• DP(46) (rss)
• geometry&phycise(13) (rss)
• graph(47) (rss)
• numberic(8) (rss)
• others(5) (rss)
• search(23) (rss)
• simple problem~(15) (rss)
• string algorithm(11) (rss)
• ujs acm training(4) (rss)

文章分類(2)

• combination math (rss)
• data struct (rss)
• DP (rss)
• graph theory(1) (rss)
• numberic (rss)
• others(1) (rss)
• search (rss)

OJ

• lunzi
• whu fatboy_cw
• yzu大牛

最新隨筆

搜索

積分與排名

• 積分 - 56621
• 排名 - 408

最新評論

閱讀排行榜