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

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久久无码精品午夜|
色欲av伊人久久大香线蕉影院|
久久久久成人精品无码中文字幕
|
精品久久久久香蕉网|
精品一区二区久久|
久久综合伊人77777|
亚洲乱码中文字幕久久孕妇黑人|
婷婷五月深深久久精品|
久久精品这里热有精品|
精品久久久久久无码国产|
香蕉aa三级久久毛片|
久久99精品国产自在现线小黄鸭|
久久精品免费大片国产大片|
色妞色综合久久夜夜|
欧美精品丝袜久久久中文字幕|
亚洲国产美女精品久久久久∴|
国产女人aaa级久久久级|
亚洲精品无码久久久久久|
久久久久九九精品影院|
久久大香香蕉国产|
久久精品aⅴ无码中文字字幕不卡|
久久精品水蜜桃av综合天堂|
伊人久久亚洲综合影院|
伊人丁香狠狠色综合久久|
久久精品国产亚洲AV香蕉|
色天使久久综合网天天|
狠狠久久综合|
青青草原综合久久|
狠狠色丁香婷婷久久综合不卡|
久久经典免费视频|
四虎影视久久久免费|
99久久精品国产一区二区蜜芽|
国产午夜福利精品久久2021|
久久久这里有精品|
亚洲国产成人精品女人久久久|
国产免费福利体检区久久|
香蕉久久一区二区不卡无毒影院|
97久久超碰成人精品网站|
日产精品久久久久久久性色
|
国产精品99久久久久久猫咪|
97久久综合精品久久久综合|