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

            USACO 1.1 Broken Necklace

            題目鏈接:http://ace.delos.com/usacoprob2?a=RfmQrEONAFb&S=beads

            今天開始重做usaco了。上次是去年這個時候了,一眨眼一年就過去了。做了兩個月才到4.3,后來就沒做了。
            現在重新開始吧。

            beads這題,比較巧妙的地方就是把字符串復制一份,從而就避免了邊界檢查。
            用left[0][i]來記錄從某一點向左可以收集到的最長r色beads數
            用left[1][i]來記錄從某一點向左可以收集到的最長b色beads數
            right數組類推。

            顯然,如果i為r色,則向左可以收集到的最長r色為left[0][i-1]+1.可以向左收集到的最長b色為0。
            如果i為b色,類推。
            如果i為w色,i即可做r,也可做b.所以各自加1.

            代碼如下:
            #include <iostream>
            #include 
            <fstream>

            using namespace std;

            ifstream fin(
            "beads.in");
            ofstream fout(
            "beads.out");

            #ifdef _DEBUG
            #define out cout
            #define in cin
            #else
            #define out fout
            #define in fin
            #endif

            //為簡化代碼,在數組前后各加1位,這樣i+1,i-1不會越界,也無需對邊界情況特殊處理。
            int l[2][702];
            int r[2][702];


            void solve()
            {
                
            int num;
                
            in>>num;

                
            string s;
                
            in>>s;
                s
            +=s;

                memset(r,
            0,sizeof(l));
                memset(r,
            0,sizeof(r));

                
            for(int i=s.size();i>=1;--i){
                    
            if(s[i-1]=='r'){
                        r[
            0][i] = r[0][i+1]+1;
                        r[
            1][i] = 0;
                    }
            else if(s[i-1]=='b'){
                        r[
            0][i] = 0;
                        r[
            1][i] = r[1][i+1]+1;
                    }
            else{
                        r[
            0][i] = r[0][i+1]+1;
                        r[
            1][i] = r[1][i+1]+1;
                    }
                }

                
            for(int i=1;i<=s.size();++i){
                    
            if(s[i-1]=='r'){
                        l[
            0][i] = l[0][i-1]+1;
                        l[
            1][i] = 0;
                    }
            else if(s[i-1]=='b'){
                        l[
            0][i] = 0;
                        l[
            1][i] = l[1][i-1]+1;
                    }
            else{
                        l[
            0][i] = l[0][i-1]+1;
                        l[
            1][i] = l[1][i-1]+1;
                    }
                }

                
            int res = INT_MIN;

                
            for(int i=1;i<=num;++i){
                    res 
            = max(res, max(r[0][i],r[1][i])+max(l[0][i+num-1],l[1][i+num-1]));
                }

                
            // 在出現重疊的情況下,res會大于num.最大只能是num
                res = min(res,num);

                
            out<<res<<endl;
            }

            int main(int argc,char *argv[])
            {
                solve();
                
            return 0;
            }




            posted on 2009-06-04 20:54 YZY 閱讀(1043) 評論(0)  編輯 收藏 引用 所屬分類: AlgorithmUSACO

            導航

            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国产激情久久久久影院老熟女| 99久久精品费精品国产一区二区| 亚洲国产精品人久久| 婷婷综合久久狠狠色99h| 国产精品青草久久久久福利99 | 欧洲精品久久久av无码电影| 久久久久亚洲AV无码永不| 97久久精品人人做人人爽| 久久久久国产一区二区三区| 伊人久久大香线蕉av一区| 青青草原综合久久| 亚洲AV日韩AV天堂久久| 精品久久久无码中文字幕| 久久亚洲精品成人AV| 国产精品久久久99| 中文字幕无码久久精品青草| 无码人妻少妇久久中文字幕蜜桃| 中文字幕成人精品久久不卡| 久久久一本精品99久久精品88| 亚洲国产成人久久综合一 | 亚洲精品乱码久久久久久久久久久久| 国产亚洲精品自在久久| 久久久久精品国产亚洲AV无码| 99久久综合国产精品二区| 久久无码人妻一区二区三区| 日韩人妻无码一区二区三区久久99 | 国产成人精品久久| 999久久久免费精品国产| 久久亚洲中文字幕精品有坂深雪| 亚洲国产精品一区二区久久| 久久久亚洲欧洲日产国码aⅴ| 亚洲国产高清精品线久久| 久久99精品久久久久久水蜜桃| 亚洲成色WWW久久网站| 亚洲精品tv久久久久久久久| 久久精品一区二区影院| 国产精品午夜久久| 国产成人精品久久一区二区三区| 漂亮人妻被黑人久久精品| 久久香综合精品久久伊人| 国产精品毛片久久久久久久|