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

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

            今天題解出來了~ 先看了大概思路 然后自己寫出來了~

            題目:

            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
            簡單來說就是兩個人輪流取coins,每個人每次取得個數(shù)為1- 2*n;n為上一輪對方取得數(shù)目,
            求兩個人都是用最佳策略,先取得那個家伙最多能拿到多少硬幣。貌似可以算是簡單博弈論的思想
            思路:
                    coins[1···N] 從下到上 sum[1···N] 剩下 i個的和
                    找到無后效性的子問題。考慮在還剩下p個錢幣時候的情況,此時可以拿k個錢
            由于條件,k的大小受上一輪拿的個數(shù)i的限制 ,所以我們要加上一個變量i。得到
            dp[p][i]這個子問題。那么容易得到
            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]}
            按照這個可以得到一個O(N^3)的算法

            oidsolve(){
              
            for(inti=1;i<=N;i++)
            //剩下i個
                   
            for(intj=1;j<=N;j++)
            //上一人拿了j 個
                       
            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
            ];
            }

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

            然后,由于考慮j的范圍 應該為 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個
            for(int j=1;j<= N-i +1;j++){ // 上次拿了j個
            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]);

            很晚了 ,先寫這么多 ,有空把bronze的寫了

            3個月后注:事實證明,當時么有時間 ~以后更沒有時間 ~~~ hoho`````````~~~~~~~``````````

            久久久久久青草大香综合精品| 久久久久久国产精品美女| 久久99精品国产自在现线小黄鸭| 亚洲午夜久久久久久噜噜噜| 性高湖久久久久久久久| 午夜精品久久久久久久久| 99国产欧美精品久久久蜜芽| av午夜福利一片免费看久久| 2021国产成人精品久久| 久久精品国产只有精品66| 97精品国产97久久久久久免费 | 蜜臀av性久久久久蜜臀aⅴ | 国产午夜精品久久久久免费视| 久久电影网2021| 亚洲国产成人乱码精品女人久久久不卡| 亚洲精品无码久久毛片| 精品少妇人妻av无码久久| 国内精品久久久久影院网站| 伊人久久亚洲综合影院| 精品久久久久久中文字幕人妻最新| 国产精品久久久久久久午夜片| 久久国产欧美日韩精品| 国产精品久久久久乳精品爆| 久久精品国产亚洲av日韩| 午夜精品久久久久9999高清| 人人狠狠综合久久亚洲88| 色偷偷88888欧美精品久久久 | 国产精品99久久久精品无码| 中文字幕亚洲综合久久| 久久久免费精品re6| 亚洲人成网亚洲欧洲无码久久| 国产精品美女久久久免费| 精品久久久久久国产潘金莲| 99久久这里只精品国产免费 | 亚洲?V乱码久久精品蜜桃| 久久激情亚洲精品无码?V| 97精品国产91久久久久久| 久久精品毛片免费观看| 久久人爽人人爽人人片AV| 亚洲精品乱码久久久久久蜜桃图片 | 久久777国产线看观看精品|