• <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 09NOV] silver xoinc [dp]

            Posted on 2009-11-12 00:20 rikisand 閱讀(513) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): AlgorithmUSACO

            周六第一次做usaco玩,bronze的輕松切掉,然后申請(qǐng)promote,下午批準(zhǔn),話說(shuō)rob 效率好高啊~ 于是繼續(xù)做silver 就遇到這個(gè)題- -!糾結(jié)了半天放棄····知道是dp 也考慮了方法就是 理不清楚;不知道是不是一天沒(méi)吃飯的緣故·····

            今天題解出來(lái)了~ 先看了大概思路 然后自己寫(xiě)出來(lái)了~

            題目:

            Farmer John's cows like to play coin games so FJ has invented with
            a new two-player coin game called Xoinc for them.
            
            Initially a stack of N (5 <= N <= 2,000) coins sits on the ground;
            coin i from the top has integer value C_i (1 <= C_i <= 100,000).
            The first player starts the game by taking the top one or two coins
            (C_1 and maybe C_2) from the stack. If the first player takes just
            the top coin, the second player may take the following one or two
            coins in the next turn. If the first player takes two coins then
            the second player may take the top one, two, three or four coins
            from the stack. In each turn, the current player must take at least
            one coin and at most two times the amount of coins last taken by
            the opposing player. The game is over when there are no more coins
            to take.
            
            Afterwards, they can use the value of the coins they have taken
            from the stack to buy treats from FJ, so naturally, their purpose
            in the game is to maximize the total value of the coins they take.
            Assuming the second player plays optimally to maximize his own
            winnings, what is the highest total value that the first player can
            have when the game is over?
            
            MEMORY LIMIT: 20 MB
            
            PROBLEM NAME: xoinc
            
            INPUT FORMAT:
            
            * Line 1: A single integer: N
            
            * Lines 2..N+1: Line i+1 contains a single integer: C_i
            
            SAMPLE INPUT (file xoinc.in):
            
            5
            1
            3
            1
            7
            2
            簡(jiǎn)單來(lái)說(shuō)就是兩個(gè)人輪流取coins,每個(gè)人每次取得個(gè)數(shù)為1- 2*n;n為上一輪對(duì)方取得數(shù)目,
            求兩個(gè)人都是用最佳策略,先取得那個(gè)家伙最多能拿到多少硬幣。貌似可以算是簡(jiǎn)單博弈論的思想
            思路:
                    coins[1···N] 從下到上 sum[1···N] 剩下 i個(gè)的和
                    找到無(wú)后效性的子問(wèn)題。考慮在還剩下p個(gè)錢(qián)幣時(shí)候的情況,此時(shí)可以拿k個(gè)錢(qián)
            由于條件,k的大小受上一輪拿的個(gè)數(shù)i的限制 ,所以我們要加上一個(gè)變量i。得到
            dp[p][i]這個(gè)子問(wèn)題。那么容易得到
            dp[p][i]=max(1=<k<=i*2){SuM(p to p-k+1)+SuM(p-k to 1)-dp[p-k][k]}
                        =max(1=<k<=i*2){sum[p]-dp[p-k][k]}
            按照這個(gè)可以得到一個(gè)O(N^3)的算法

            oidsolve(){
              
            for(inti=1;i<=N;i++)
            //剩下i個(gè)
                   
            for(intj=1;j<=N;j++)
            //上一人拿了j 個(gè)
                       
            for(intk=1;k<=j*2&&i-k>=0
            ;k++){
                            dp[i][j]=max(dp[i][j],sum[
            1]-sum[i+1
            ]-dp[i-k][k]);
                        }
                ret=dp[N][
            1
            ];
            }

             三重遞歸 ,最多可以過(guò)500的數(shù)據(jù)量  觀察可以得出 dp[p][j] 和 dp[p][j+1] 的計(jì)算有很多的重疊
            因?yàn)?上次拿了j+1 則可以比 dp[p][j] 多拿 2 個(gè) 

            然后,由于考慮j的范圍 應(yīng)該為 N-i+1

            這樣得到了最終代碼:

            scanf("%d",&N);
            for(int i=1;i<=N;i++)    scanf("%d",coins+i);//{fin>>coins[i]; }
            sum[0]=0;
            for(int i=1;i<=N;i++)     sum[i]=sum[i-1]+coins[N-i+1]; 
            for(int i=1;i<=N;i++)        //剩下i個(gè)
            for(int j=1;j<= N-i +1;j++){ // 上次拿了j個(gè)
            if(dp[i][j]<dp[i][j-1])dp[i][j]=dp[i][j-1];
            if(2*j-1<=i&&dp[i][j]<sum[i]-dp[i-2*j+1][2*j-1]) dp[i][j]=sum[i]-dp[i-2*j+1][2*j-1];
            if(2*j<=i&&dp[i][j]<sum[i]-dp[i-2*j][2*j]) dp[i][j]= sum[i]-dp[i-2*j][2*j];
            }
            printf("%d\n",dp[N][1]);

            很晚了 ,先寫(xiě)這么多 ,有空把bronze的寫(xiě)了

            3個(gè)月后注:事實(shí)證明,當(dāng)時(shí)么有時(shí)間 ~以后更沒(méi)有時(shí)間 ~~~ hoho`````````~~~~~~~``````````

            2021少妇久久久久久久久久| 国内精品久久国产| 久久国产精品一区| 99久久免费国产特黄| 久久人人爽爽爽人久久久| 国产美女亚洲精品久久久综合| 婷婷久久综合| 久久久久久久波多野结衣高潮| 久久精品国产乱子伦| 狠狠色婷婷久久综合频道日韩| 狠狠色丁香婷综合久久| 亚洲中文字幕久久精品无码APP | 精品久久久久久无码中文字幕一区| 久久久久久av无码免费看大片| 久久这里的只有是精品23| 久久亚洲中文字幕精品一区| 中文字幕无码精品亚洲资源网久久| 国产成人无码精品久久久久免费| 国产色综合久久无码有码| 久久亚洲AV无码西西人体| 国产亚洲欧美成人久久片| 欧洲成人午夜精品无码区久久| 无码精品久久一区二区三区| 国内精品久久久久久中文字幕| 麻豆亚洲AV永久无码精品久久| 久久青青色综合| 久久综合偷偷噜噜噜色| 亚洲精品97久久中文字幕无码| 精品久久久久久国产免费了| 久久99国产精一区二区三区| www久久久天天com| 丰满少妇高潮惨叫久久久| 97精品久久天干天天天按摩| 亚洲国产精品成人久久| 久久亚洲精品无码VA大香大香| 中文字幕久久亚洲一区| 久久久这里有精品| 77777亚洲午夜久久多喷| 人妻久久久一区二区三区| 国产精品一区二区久久| 久久精品免费观看|