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

    
            

            




            







												


        

	
            
		

		
		
            
			
					

            
	
	int f[i][j]表示第i個(gè)字符到第j個(gè)字符需要添加的最少括號(hào)數(shù)。string ans[i][j] 表示第i個(gè)字符到第j個(gè)字符按照最優(yōu)方案添加括號(hào)后的串。狀態(tài)轉(zhuǎn)移：1.f[i][j]由f[i + 1][j - 1]轉(zhuǎn)移來(lái)（通過(guò)兩端添括號(hào)() / [] ）。2.f[i][j]由f[i][k] + f[k + 1][j]轉(zhuǎn)移來(lái)（通過(guò)串合并）。答案是ans[0][len - 1]。

            

            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2007-8-27 9:54:57
            File Name: pku1141.cpp
            Description: 
            ***********************************************************************            */
            #include             <iostream>
            using namespace std;
            #define out(x) (cout << #x << ": " << x << endl)
            const int maxint = 0x7FFFFFFF;
            typedef             long long int64;
            const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
            template             <class T> void show(T a, int n) {for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
            template             <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

            const int maxn = 110;

            char s[maxn];
            int len;

            int f[maxn][maxn];
            string ans[maxn][maxn];

            void dp()
            {
                memset(f,             0, sizeof(f));
                            for (int i = 0; i < len; i++)
                                for (int j = i; j < len; j++)
                                {
                        f[i][j]             = maxint;
                        ans[i][j]             = "";
                    }
                            for (int i = len - 1; i >= 0; i--)
                                for (int j = i; j < len; j++)
                                    if (i == j)
                                    {
                            f[i][j]             = 1;
                                        if (s[i] == '(') ans[i][j] = "()";
                                        if (s[i] == ')') ans[i][j] = "()";
                                        if (s[i] == '[') ans[i][j] = "[]";
                                        if (s[i] == ']') ans[i][j] = "[]";
                        }
                                    else
                                    {
                                        if (j > i)
                                        {
                                            if (s[i] == '(' && s[j] == ')')
                                            {
                                                if (f[i + 1][j - 1] < f[i][j])
                                                {
                                        f[i][j]             = f[i + 1][j - 1];
                                        ans[i][j]             = "(" + ans[i + 1][j - 1] + ")";
                                    }
                                }
                                            else if (s[i] == '[' && s[j] == ']')
                                            {
                                                if (f[i + 1][j - 1] < f[i][j])
                                                {
                                        f[i][j]             = f[i + 1][j - 1];
                                        ans[i][j]             = "[" + ans[i + 1][j - 1] + "]";
                                    }                                        
                                }
                            }
                                        for (int k = i; k < j; k++)
                                        {
                                            if (f[i][k] + f[k + 1][j] < f[i][j])
                                            {
                                    f[i][j]             = f[i][k] + f[k + 1][j];
                                    ans[i][j]             = ans[i][k] + ans[k + 1][j];
                                }
                            }
                        }
            }

            int main()
            {
                            while (scanf("%s", s) != EOF)
                            {
                    len             = strlen(s);
                    dp();
                    cout             << ans[0][len - 1] << endl;
                }
                            return 0;
            }
            

	
            
		posted on 2007-08-27 15:55 Felicia 閱讀(1246) 評(píng)論(3)  編輯 收藏 引用  所屬分類: 動(dòng)態(tài)規(guī)劃 
	
            

            
	
	





            
	    
    


            
	
            
		Comments
	
            
		
	
			
              
		
			
            • 
				
              
					# re: [動(dòng)態(tài)規(guī)劃]pku1141
				
              
				l-y-p
              
				Posted @ 2008-03-03 11:36
              
				你的這個(gè)代碼提交也WA，不知是怎么回事，自己也寫(xiě)了兩個(gè)代碼，也都WA，感覺(jué)都沒(méi)錯(cuò)，但結(jié)果卻WA  回復(fù)  更多評(píng)論
				  
			
              • 
		
			
            • 
				
              
					# re: [動(dòng)態(tài)規(guī)劃]pku1141
				
              
				wobat
              
				Posted @ 2008-07-01 16:27
              
				對(duì)空的輸入，要輸出回車。。

              也缺了#include<string>。。

              其他的都對(duì)了  回復(fù)  更多評(píng)論
				  
			
              • 
		
			
            • 
				
              
					# re: [動(dòng)態(tài)規(guī)劃]pku1141
				
              
				wwq
              
				Posted @ 2012-07-06 17:34
              
				你的這個(gè)代碼提交WA了  回復(fù)  更多評(píng)論
				  
			
              • 
		
			
            
		

            







            






            

				
			
             
            
		
            
		

	
            

            


                
    







            
	   
	



久久国产精品成人影院|
国产精品久久毛片完整版|
日本免费一区二区久久人人澡|
亚洲中文久久精品无码ww16|
久久久久亚洲av成人无码电影|
久久亚洲AV无码西西人体|
久久综合综合久久狠狠狠97色88|
久久久久久人妻无码|
久久久久久午夜成人影院|
亚洲国产美女精品久久久久∴
|
无码人妻久久一区二区三区|
亚洲欧美伊人久久综合一区二区|
模特私拍国产精品久久|
久久无码中文字幕东京热|
久久久久精品国产亚洲AV无码|
久久亚洲国产精品成人AV秋霞
|
免费精品99久久国产综合精品|
国产产无码乱码精品久久鸭|
欧美牲交A欧牲交aⅴ久久|
日日躁夜夜躁狠狠久久AV|
久久精品国产久精国产思思|
久久亚洲精品中文字幕三区|
久久久久18|
大香伊人久久精品一区二区
|
久久婷婷是五月综合色狠狠|
久久亚洲精品无码VA大香大香|
亚洲中文字幕久久精品无码喷水|
成人妇女免费播放久久久|
91久久九九无码成人网站|
久久精品二区|
亚洲av日韩精品久久久久久a
|
久久综合九色综合久99|
久久精品青青草原伊人|
国产成人精品久久免费动漫|
久久精品夜色噜噜亚洲A∨|
国产香蕉久久精品综合网|
狠狠色婷婷久久一区二区三区|
国产—久久香蕉国产线看观看|
2021最新久久久视精品爱|
精品久久久久久中文字幕|
久久无码人妻精品一区二区三区|