• <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 幻浪天空領(lǐng)主 閱讀(235) 評(píng)論(0)  編輯 收藏 引用 所屬分類: USACO

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

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久国产精品无码HDAV| 热久久这里只有精品| 欧美久久久久久| 国产精品欧美久久久天天影视 | 精品久久久久久无码中文野结衣| 合区精品久久久中文字幕一区 | 亚洲国产成人精品女人久久久 | 伊人久久大香线蕉无码麻豆| www亚洲欲色成人久久精品| 久久久久久久久久久久中文字幕 | 久久精品中文无码资源站| 精品久久久久国产免费| 亚洲女久久久噜噜噜熟女| 亚洲欧洲中文日韩久久AV乱码| 久久人人爽人人爽人人AV| 少妇熟女久久综合网色欲| 婷婷国产天堂久久综合五月| 免费国产99久久久香蕉| 久久久无码精品亚洲日韩京东传媒 | 久久涩综合| 亚洲一级Av无码毛片久久精品| 久久综合九色综合欧美狠狠| 国产亚洲欧美精品久久久| 东京热TOKYO综合久久精品| 精品综合久久久久久98| 亚洲人成网站999久久久综合| 久久综合九色综合97_久久久| 国产精品99精品久久免费| 久久国产精品一国产精品金尊| 亚洲国产美女精品久久久久∴| 久久久久久精品成人免费图片| 亚洲天堂久久久| 久久一区二区三区99| 久久中文字幕无码专区| 久久精品无码一区二区三区日韩| 久久亚洲中文字幕精品一区| 久久伊人五月丁香狠狠色| 精品综合久久久久久97| 精品国际久久久久999波多野| 久久夜色精品国产噜噜麻豆| 久久91精品国产91久久小草|