• <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>
            

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			pku1335 Digital Onion 遞歸
		
            
		題意：
            定義括號(hào)序列：
            Definition: Null parenthesis is a DO. Especially, we call this the Null DO. 
            Definition: "( )" is a DO. Especially, we call this the primitive DO. 
            Definition: If both A and B are DOs, then the combined form of "(A)B" is also a DO, where we call A the inside of the DO and B the outside of the DO. 
            定義排序規(guī)則：
            [Rule1]: The more weight, the more expensive. 
            [Rule2]: If the weights of two DOs are equal, then the price depends on the inside DO of the two DOs. 
            [Rule3]: If the weights of two DOs are the same and the prices of the inside DOs are equal, then the price depends on the outside DO of the two DOs. 
            給出一個(gè)符號(hào)序列，求這個(gè)之后的一個(gè)符號(hào)序列是什么

            思路：
            首先要確定最小的符號(hào)序列為：（）（）（）...
            然后就是轉(zhuǎn)化方法：
            對(duì)于一個(gè)符號(hào)序列(inside)outside，首先看outside能否+1，不行的話看inside能否+1，同時(shí)將outside置為最小值形式，再不行的話當(dāng)outside不為空的時(shí)候?qū)nside的weight+1,outside's weight-1，將兩部分都轉(zhuǎn)化為最小值形式。
            以上描述的是一個(gè)遞歸過(guò)程~當(dāng)然，考慮一種特殊情況，如果整個(gè)式子無(wú)法進(jìn)行+1操作，只能將整個(gè)式子的weight+1,然后化為最小值形式。

            發(fā)現(xiàn)java的string竟然是值傳遞，非常的蛋疼。。我喜歡java的String，沒辦法，只好用C++的string。。。這種字符串處理的題目string是非常給力的~

            代碼：
            

             1# include <iostream>
             2# include <string>
             3# include <cstring>
             4using namespace std;
             5string str;
             6void make(int s,int e,int type)
             7{
             8    int c=0;
             9    for(int i=s;i<e;i++)
            10        if(str[i]=='(')
            11            c++;
            12    c+=type;
            13    string res="";
            14    for(int i=0;i<c;i++) res+="()";
            15    str=str.substr(0,s)+res+str.substr(e,str.length()-e);
            16}
            17bool solve(int s,int e)
            18{
            19    if(s==e) return false;
            20    else
            21    {
            22        int c=-1,end;
            23        for(end=s+1;end<e&&c;end++)
            24            switch(str[end])
            25            {
            26            case '(':c--;break;
            27            case ')':c++;break;
            28            }            ;
            29        if(solve(end,e)) return true;
            30        else if(solve(s+1,end-1))
            31        {
            32            make(end,e,0);
            33            return true;
            34        }
            35        else if(end!=e)
            36        {
            37            make(end,e,-1);
            38            make(s+1,end-1,1);
            39            return true;
            40        }
            41        else return false;
            42    }
            43}
            44int main()
            45{
            46    int test;
            47    cin>>test;
            48    while(test--)
            49    {
            50        str.clear();
            51        while(true)
            52        {
            53            string tmp;
            54            cin>>tmp;
            55            if(tmp=="$") break;
            56            str+=tmp;
            57        }
            58        if(!solve(0,str.length())) make(0,str.length(),1);
            59        for(int i=0;i<str.length();i++)
            60            cout<<str[i]<<" ";
            61        cout<<"$"<<endl;
            62    }
            63    return 0;
            64}
            

            

		
            
			posted on 2011-01-25 01:01 yzhw 閱讀(258) 評(píng)論(0)  編輯 收藏 引用  所屬分類: DP 
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2011年1月>
            
	
            日一二三四五六
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345
            

            

					

            導(dǎo)航
            

					

            統(tǒng)計(jì)
            
	
					

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

					

            留言簿(1)
            


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


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評(píng)論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



精品国产热久久久福利|
久久久久99精品成人片试看|
国产精品久久久久aaaa|
久久精品国产亚洲综合色|
国产精品成人精品久久久|
亚洲精品综合久久|
狠狠色丁香久久婷婷综|
亚洲精品视频久久久|
久久w5ww成w人免费|
久久综合视频网站|
久久精品国产半推半就|
亚洲精品第一综合99久久|
99久久久精品|
久久精品国产99久久久古代|
久久久国产精品网站|
午夜精品久久久久久久久|
久久人人爽人人爽人人片AV麻豆
|
一本久久a久久精品综合香蕉|
欧洲成人午夜精品无码区久久|
久久国产热这里只有精品|
久久久久久a亚洲欧洲aⅴ|
久久综合久久综合亚洲|
日本高清无卡码一区二区久久|
久久综合欧美成人|
久久精品国产亚洲av水果派
|
伊人色综合久久天天人手人婷|
久久久精品国产Sm最大网站|
日本久久久精品中文字幕|
亚洲中文久久精品无码|
国产69精品久久久久APP下载|
久久久久国产一区二区三区|
99热热久久这里只有精品68|
久久综合中文字幕|
99精品伊人久久久大香线蕉|
91超碰碰碰碰久久久久久综合|
精品精品国产自在久久高清|
亚洲狠狠久久综合一区77777|
热久久这里只有精品|
伊人色综合久久|
久久人人爽人爽人人爽av|
亚洲人成电影网站久久|