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

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久婷婷激情综合色综合俺也去| 精品国产乱码久久久久软件| 久久综合九色欧美综合狠狠| 国产精品一久久香蕉国产线看观看 | 热久久这里只有精品| 中文国产成人精品久久不卡 | 久久亚洲欧洲国产综合| 久久播电影网| 国产精品内射久久久久欢欢| 国产精品日韩深夜福利久久| 草草久久久无码国产专区| 国产精品久久久久久久午夜片| AAA级久久久精品无码区| 精品无码久久久久久久久久| 国产精自产拍久久久久久蜜| 日韩中文久久| 亚洲AV无码久久精品成人| 国产午夜免费高清久久影院| 色综合久久综精品| yy6080久久| 精品久久久久久中文字幕人妻最新| 97久久天天综合色天天综合色hd| 热re99久久精品国产99热| 无码任你躁久久久久久| 97精品依人久久久大香线蕉97| 久久精品国产精品青草| 伊人久久大香线蕉精品不卡| 欧美精品久久久久久久自慰| 国产精品免费看久久久香蕉| 狠狠色噜噜色狠狠狠综合久久| 久久中文娱乐网| 久久久久久久久久久精品尤物| 天天久久狠狠色综合| 热久久视久久精品18| 国产精品久久久久无码av| 久久99热这里只频精品6| 久久99精品国产99久久| 亚洲精品无码久久久影院相关影片| 久久综合久久综合九色| 亚洲第一极品精品无码久久| 久久人人爽人人爽人人片AV麻豆|