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


            動態規劃法。
            用dp[player][start][end]表示player在[start..end]會取得的最大值。
            如果player==0,那么player有主動權,它要么選start,要么選end.顯然,它要選使得對手得分最少的那一個。
            當它選start時,對手所能到的最大值為dp[1][start+1][end]。當它選end時,對手所選的最大值是dp[1][start][end-1].
            。所以我們選dp[1][start+1][end]和dp[1][start][end-1]中小的那一個。
            如果player==1,那只能被動的等0先選了。1在剩下區段中,又作為先選的角色,即player0。
            當只有一個數字的時候,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 閱讀(302) 評論(0)  編輯 收藏 引用 所屬分類: AlgorithmUSACO 、動態規劃

            導航

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

            統計

            常用鏈接

            留言簿(2)

            隨筆分類

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            色狠狠久久综合网| 国产真实乱对白精彩久久| 久久免费看黄a级毛片| 久久无码AV中文出轨人妻| 亚洲va中文字幕无码久久不卡| 97久久香蕉国产线看观看| 久久精品成人免费网站| 色8激情欧美成人久久综合电| 久久人人爽人人爽人人AV| 久久不射电影网| 亚洲欧洲久久av| 国产精品久久久久无码av| 青春久久| 国产伊人久久| 久久亚洲国产欧洲精品一| 色综合久久88色综合天天 | 国产精品禁18久久久夂久| 91精品国产综合久久精品| 亚洲午夜精品久久久久久app| 久久久久久免费一区二区三区 | 久久精品亚洲一区二区三区浴池| 夜夜亚洲天天久久| 人妻无码久久一区二区三区免费| 久久久久久国产精品美女| 国产69精品久久久久9999| 综合久久久久久中文字幕亚洲国产国产综合一区首 | 色欲久久久天天天综合网精品 | 狠狠人妻久久久久久综合蜜桃| 亚洲中文字幕无码久久精品1 | 亚洲精品tv久久久久久久久 | 亚洲欧洲中文日韩久久AV乱码| 91久久成人免费| 久久99精品国产| 2021精品国产综合久久| 国产V亚洲V天堂无码久久久| 久久久久亚洲AV成人片 | www.久久99| 国产精品久久久久无码av| 天天久久狠狠色综合| 国产精品嫩草影院久久| 久久久精品波多野结衣|