• <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 3.3 A Game


            動態(tài)規(guī)劃法。
            用dp[player][start][end]表示player在[start..end]會取得的最大值。
            如果player==0,那么player有主動權(quán),它要么選start,要么選end.顯然,它要選使得對手得分最少的那一個。
            當(dāng)它選start時,對手所能到的最大值為dp[1][start+1][end]。當(dāng)它選end時,對手所選的最大值是dp[1][start][end-1].
            。所以我們選dp[1][start+1][end]和dp[1][start][end-1]中小的那一個。
            如果player==1,那只能被動的等0先選了。1在剩下區(qū)段中,又作為先選的角色,即player0。
            當(dāng)只有一個數(shù)字的時候,player0就只有選這個,player1就沒得選,返回0.
            代碼如下:

            #include?<iostream>
            #include?
            <fstream>

            using?namespace?std;

            ifstream?fin(
            "game1.in");
            ofstream?fout(
            "game1.out");

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

            int?dp[2][100][100];
            int?sequence[100];

            int?score(int?player,int?start,int?end)
            {
            ????
            if(dp[player][start][end]!=-1)
            ????????
            return?dp[player][start][end];

            ????
            if(start==end){
            ????????
            if(player==0)
            ????????????dp[player][start][end]?
            =?sequence[start];
            ????????
            else?
            ????????????dp[player][start][end]?
            =?0;
            ????}
            else{
            ????????
            int?t1?=?score(0,start+1,end);
            ????????
            int?t2?=?score(0,start,end-1);
            ????????
            if(player==0){
            ????????????
            if(t1>t2){
            ????????????????dp[player][start][end]?
            =?sequence[end]+score(1,start,end-1);
            ????????????}
            else{
            ????????????????dp[player][start][end]?
            =?sequence[start]+score(1,start+1,end);
            ????????????}
            ????????}
            else{
            ????????????
            if(t1>t2){
            ????????????????dp[player][start][end]?
            =?score(0,start,end-1);
            ????????????}
            else{
            ????????????????dp[player][start][end]?
            =?score(0,start+1,end);
            ????????????}
            ????????}
            ????}

            ????
            return?dp[player][start][end];
            }

            void?solve()
            {
            ????memset(dp,
            -1,sizeof(dp));

            ????
            int?size;
            ????
            in>>size;

            ????
            for(int?i=0;i<size;++i)
            ????????
            in>>sequence[i];

            ????
            out<<score(0,0,size-1)<<"?"<<score(1,0,size-1)<<endl;
            }

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


            posted on 2009-07-09 13:50 YZY 閱讀(303) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm 、USACO動態(tài)規(guī)劃

            導(dǎo)航

            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            統(tǒng)計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国产精品伦理久久久久久| 77777亚洲午夜久久多人| 午夜不卡久久精品无码免费| 精品乱码久久久久久久| 国产精品综合久久第一页| 日韩精品无码久久一区二区三 | 伊人久久大香线蕉成人| 国产国产成人精品久久| 久久人人超碰精品CAOPOREN| 久久国产乱子精品免费女| 色婷婷久久综合中文久久一本 | 久久精品成人国产午夜| 四虎国产精品免费久久| 久久精品国产一区二区三区日韩| 一级做a爰片久久毛片看看| 久久AⅤ人妻少妇嫩草影院| 99久久婷婷国产一区二区| 国内精品久久国产大陆| 久久亚洲sm情趣捆绑调教 | 久久精品国产2020| 久久人与动人物a级毛片| 久久精品免费网站网| 久久久久久久综合综合狠狠| 国内精品久久久久久野外| av色综合久久天堂av色综合在| 久久精品成人免费国产片小草| 久久99热狠狠色精品一区| 久久夜色精品国产噜噜亚洲AV| 久久99精品久久久久久久久久| 欧美日韩精品久久免费| 伊人久久一区二区三区无码| 久久乐国产精品亚洲综合| 久久久精品波多野结衣| 久久综合狠狠综合久久97色| 一本大道加勒比久久综合| 狠狠色丁香久久综合婷婷| 2021久久精品国产99国产精品| 99国产欧美久久久精品蜜芽| 久久夜色精品国产亚洲| 青青热久久国产久精品| 亚洲一区精品伊人久久伊人|