• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			pku2138 Travel Games DP找最長鏈
		
            
		題意是這樣
            給出一些字符串，如果字符串i可以由字符串j刪除一個字母而獲得，則字符串i可以導(dǎo)出字符串j。
            現(xiàn)求以固定字符串開頭的最長鏈
            把字符串看成圖的節(jié)點，一次DP即可~
            預(yù)處理的時候有點技巧，先對字符串按其長度排序，然后線掃+Hash即可在線性時間內(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)

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


	


            
	    
    




            






            

				
				

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

            

					

            導(dǎo)航
            

					

            統(tǒng)計
            
	
					

            公告
            
	
            統(tǒng)計系統(tǒng)
            

					

            留言簿(1)
            


		
            隨筆分類(227)
            
		
				
			
	
		
            文章分類(2)
            
		
				
			
	
		
            OJ
            
		
				
			
	


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



91精品国产91久久|
91精品国产高清久久久久久io|
中文字幕久久波多野结衣av|
久久久黄色大片|
久久水蜜桃亚洲av无码精品麻豆
|
久久国产成人|
天天影视色香欲综合久久|
久久久亚洲裙底偷窥综合|
精品久久久久久亚洲精品|
97精品伊人久久久大香线蕉|
亚洲欧美国产精品专区久久|
日本欧美久久久久免费播放网|
国产精品久久久久久久午夜片
|
久久久久免费看成人影片|
国产精品日韩深夜福利久久|
久久婷婷午色综合夜啪|
日韩欧美亚洲综合久久影院d3|
无码人妻久久一区二区三区蜜桃
|
久久久精品国产sm调教网站|
国产一区二区精品久久岳
|
狠狠精品久久久无码中文字幕
|
中文精品99久久国产|
久久精品一区二区三区不卡|
波多野结衣AV无码久久一区|
国产精品内射久久久久欢欢|
久久久亚洲欧洲日产国码二区
|
国产精品免费福利久久|
无码8090精品久久一区|
国产成人精品久久一区二区三区av|
伊人久久大香线蕉av一区|
蜜臀久久99精品久久久久久
|
久久精品一区二区国产|
久久精品卫校国产小美女|
久久久久久av无码免费看大片|
久久精品视频网|
久久香蕉综合色一综合色88|
欧美丰满熟妇BBB久久久|
国产成人久久精品一区二区三区|
污污内射久久一区二区欧美日韩
|
狠狠色综合网站久久久久久久
|
欧美精品久久久久久久自慰|