• <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 遞歸
		
            
		題意：
            定義括號序列：
            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. 
            定義排序規則：
            [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. 
            給出一個符號序列，求這個之后的一個符號序列是什么

            思路：
            首先要確定最小的符號序列為：（）（）（）...
            然后就是轉化方法：
            對于一個符號序列(inside)outside，首先看outside能否+1，不行的話看inside能否+1，同時將outside置為最小值形式，再不行的話當outside不為空的時候將inside的weight+1,outside's weight-1，將兩部分都轉化為最小值形式。
            以上描述的是一個遞歸過程~當然，考慮一種特殊情況，如果整個式子無法進行+1操作，只能將整個式子的weight+1,然后化為最小值形式。

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


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年10月>
            
	
            日一二三四五六
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456
            

            

					

            導航
            

					

            統計
            
	
					

            公告
            
	
            統計系統
            

					

            留言簿(1)
            


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


            最新隨筆
            




            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久人人爽人人爽人人片AV不|
国产精品无码久久久久|
久久综合亚洲色HEZYO社区|
国产aⅴ激情无码久久|
久久青青草原亚洲av无码app|
韩国无遮挡三级久久|
久久久久亚洲爆乳少妇无|
久久无码人妻一区二区三区|
久久激情亚洲精品无码?V|
中文字幕无码精品亚洲资源网久久
|
色欲久久久天天天综合网|
国产精品一久久香蕉产线看|
人妻无码精品久久亚瑟影视|
99久久婷婷免费国产综合精品|
亚洲国产一成久久精品国产成人综合
|
久久久久久噜噜精品免费直播|
亚洲色大成网站WWW久久九九|
成人a毛片久久免费播放|
97精品国产97久久久久久免费|
精品水蜜桃久久久久久久|
久久精品国产第一区二区三区|
久久久久国产亚洲AV麻豆|
1000部精品久久久久久久久|
久久精品中文字幕一区|
人妻中文久久久久|
久久国产午夜精品一区二区三区|
久久久久人妻精品一区|
亚洲精品乱码久久久久久自慰|
青青久久精品国产免费看
|
国产精品99久久免费观看|
国产一区二区久久久|
欧美国产精品久久高清|
精品国产乱码久久久久久浪潮|
久久久久久久99精品免费观看|
东京热TOKYO综合久久精品|
久久久久久九九99精品|
狠狠色婷婷久久一区二区三区|
久久久精品国产sm调教网站
|
久久久中文字幕|
国产精品九九久久免费视频
|
国产精品伦理久久久久久|