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

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            97久久国产亚洲精品超碰热| 久久久久亚洲av成人无码电影| 久久人人爽人人爽人人片AV东京热 | 亚洲AV成人无码久久精品老人| 久久久久久亚洲精品影院| 国产偷久久久精品专区| 久久se精品一区二区| 久久久久久精品久久久久| 久久99国产精品一区二区| 久久国产AVJUST麻豆| 99久久国语露脸精品国产| 亚洲国产成人精品女人久久久| 亚洲午夜久久久影院| 久久国产高清一区二区三区| 亚洲精品无码久久久久去q| 精品多毛少妇人妻AV免费久久| 一本一道久久综合狠狠老| 久久久WWW免费人成精品| 99久久er这里只有精品18| 久久久久久综合网天天| 精品久久久久久久久久中文字幕 | 久久大香萑太香蕉av| 7国产欧美日韩综合天堂中文久久久久 | 无码人妻久久一区二区三区蜜桃| 久久国产精品-久久精品| 伊人久久大香线蕉av一区| 欧美久久久久久午夜精品| 日韩精品国产自在久久现线拍| 久久久久女人精品毛片| 国产激情久久久久久熟女老人| 亚洲欧洲精品成人久久奇米网| 一本色道久久88加勒比—综合| 青青草国产精品久久久久| 国产美女久久精品香蕉69| 99久久无码一区人妻a黑| 欧美丰满熟妇BBB久久久| 久久久久成人精品无码| 久久婷婷五月综合色奶水99啪| 精产国品久久一二三产区区别| 热久久最新网站获取| 亚洲中文字幕无码久久综合网|