久久亚洲国产成人影院网站,武侠古典久久婷婷狼人伊人,狠狠色综合网站久久久久久久高清

pku2138 Travel Games DP找最長鏈

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

import java.io.*;
2

import java.util.*;
3

public class Main {
4

/**
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

}
68

posted on 2010-11-01 22:21 yzhw 閱讀(229) 評論(0) 編輯收藏引用所屬分類: DP 、graph

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

pku2138 Travel Games DP找最長鏈

導(dǎo)航

統(tǒng)計(jì)

公告

留言簿(1)

隨筆分類(227)

文章分類(2)

OJ

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜