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

            A Game

            IOI'96 - Day 1

            Consider the following two-player game played with a sequence of N positive integers (2 <= N <= 100) laid onto a game board. Player 1 starts the game. The players move alternately by selecting a number from either the left or the right end of the sequence. That number is then deleted from the board, and its value is added to the score of the player who selected it. A player wins if his sum is greater than his opponents.

            Write a program that implements the optimal strategy. The optimal strategy yields maximum points when playing against the "best possible" opponent. Your program must further implement an optimal strategy for player 2.

            PROGRAM NAME: game1

            INPUT FORMAT

            Line 1: N, the size of the board
            Line 2-etc: N integers in the range (1..200) that are the contents of the game board, from left to right

            SAMPLE INPUT (file game1.in)

            6
            4 7 2 9
            5 2
            

            OUTPUT FORMAT

            Two space-separated integers on a line: the score of Player 1 followed by the score of Player 2.

            SAMPLE OUTPUT (file game1.out)

            18 11
            

            Analysis

            A typical game theory problem. The problem aims to find a solution for two players, which impletement optimal strategy for player 2. Considering the fact of only two operations for each step, making dynamic programming is helpful for these. F[i][j] is defined as the maximum sum for player 1 when choosing numbers among range [i,j], and s[i][j] stands for the sum of numbers among ith number and jth number. After all, new an array num[i] to store numbers.
            Then, considering the two activities in choosing, which can only be happened for numbers of the first and the last one. Since the description needs an optimal strategy for player two, it is reasonable for maximum the result.
            After all, the function can be presented below: f[i][j]=max{num[i]+sum[i+1][j]-f[i+1][j],num[j]+sum[i][j-1]-f[i][j-1]}, 1<=i,j<=n.
            Initialization: f[i][i]=num[i], 1<=i<=n.
            Tips in calculating: just only two variables: x,k. "j" is better fixed by x+k for f[i][j] is fully determined by f[i+1][j] and f[i][j-1], which are turing into f[x+1][x+k] and f[x][x+k-1]. It is obvious to making the first "for loop" of k and the next one is "x". Otherwise, i and j are too flexible to make loops.

            Code

            /*
            ID:braytay1
            PROG:game1
            LANG:C++
            */

            #include 
            <iostream>
            #include 
            <fstream>
            using namespace std;

            int n;
            int f[100][100],num[100],sum,s[100][100];

            int max(int a,int b){
                
            return a>b?a:b;
            }


            int main(){
                ifstream fin(
            "game1.in");
                ofstream fout(
            "game1.out");
                fin
            >>n;
                
            for(int i=0;i<n;i++) fin>>num[i];
                memset(f,
            0,sizeof f);
                memset(s,
            0,sizeof s);
                
            for(int i=0;i<n;i++) f[i][i]=num[i];
                
            for(int i=0;i<n;i++)
                    
            for(int j=0;j<n;j++)
                        
            for(int k=i;k<=j;k++)
                            s[i][j]
            +=num[k];
                
            for(int k=1;k<n;k++)
                    
            for(int x=0;x+k<n;x++)        
                        f[x][x
            +k]=max(num[x]+s[x+1][x+k]-f[x+1][x+k],num[x+k]+s[x][x+k-1]-f[x][x+k-1]);
                fout
            <<f[0][n-1]<<" "<<s[0][n-1]-f[0][n-1]<<endl;
                
            return 0;
            }


             

            posted on 2008-09-01 16:36 幻浪天空領主 閱讀(235) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久久久精品妇女99| 久久久无码精品亚洲日韩京东传媒| 亚洲中文字幕伊人久久无码| 亚洲AV无码一区东京热久久| 久久99国产精品二区不卡| 欧美色综合久久久久久| 久久国产成人精品麻豆| 久久精品这里热有精品| 午夜精品久久久久久久| 99久久亚洲综合精品网站| 久久无码国产| 狠狠色综合网站久久久久久久 | 中文字幕热久久久久久久| 久久久久99精品成人片三人毛片 | 久久久久噜噜噜亚洲熟女综合| 亚洲伊人久久成综合人影院 | 无码伊人66久久大杳蕉网站谷歌| 青青草国产成人久久91网| 久久国产色av免费看| 欧美国产成人久久精品| 久久国产一区二区| 久久婷婷国产综合精品| 日韩人妻无码精品久久久不卡| 91久久精品视频| 成人国内精品久久久久一区| 国产精品久久久久无码av| 久久九九亚洲精品| 久久综合给合久久狠狠狠97色| 亚洲国产小视频精品久久久三级| 91精品国产高清久久久久久91 | 精品国产乱码久久久久久人妻 | 免费精品久久久久久中文字幕| 久久免费精品视频| 国产V亚洲V天堂无码久久久| 久久久亚洲欧洲日产国码二区| 国产午夜精品久久久久免费视 | 久久乐国产精品亚洲综合 | 狼狼综合久久久久综合网| 久久久免费精品re6| 国产精品久久波多野结衣| 久久综合九色综合97_久久久|