在线播放视频一区,亚洲曰本av电影,久久精品官网

江蘇大學

pku2138 Travel Games DP找最長鏈

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

1

import java.io.*;
2

import java.util.*;
3

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

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


相關文章: pku3903 最長遞增字串的單調性優化 pku 3998 Land Division DP斜率優化 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 管理