• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217919
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            Two Ends
            Time Limit:1000MS? Memory Limit:65536K
            Total Submit:625 Accepted:271

            Description
            In the two-player game "Two Ends", an even number of cards is laid out in a row. On each card, face up, is written a positive integer. Players take turns removing a card from either end of the row and placing the card in their pile. The player whose cards add up to the highest number wins the game. Now one strategy is to simply pick the card at the end that is the largest -- we'll call this the greedy strategy. However, this is not always optimal, as the following example shows: (The first player would win if she would first pick the 3 instead of the 4.)
            3 2 10 4
            You are to determine exactly how bad the greedy strategy is for different games when the second player uses it but the first player is free to use any strategy she wishes.

            Input
            There will be multiple test cases. Each test case will be contained on one line. Each line will start with an even integer n followed by n positive integers. A value of n = 0 indicates end of input. You may assume that n is no more than 1000. Furthermore, you may assume that the sum of the numbers in the list does not exceed 1,000,000.

            Output
            For each test case you should print one line of output of the form:
            In game m, the greedy strategy might lose by as many as p points.
            where m is the number of the game (starting at game 1) and p is the maximum possible difference between the first player's score and second player's score when the second player uses the greedy strategy. When employing the greedy strategy, always take the larger end. If there is a tie, remove the left end.

            Sample Input

            4 3 2 10 4
            8 1 2 3 4 5 6 7 8
            8 2 2 1 5 3 8 7 3
            0

            Sample Output

            In game 1, the greedy strategy might lose by as many as 7 points.
            In game 2, the greedy strategy might lose by as many as 4 points.
            In game 3, the greedy strategy might lose by as many as 5 points.

            Source
            East Central North America 2005

            #include? < iostream >
            #include?
            < cmath >
            using ? namespace ?std;

            const ? int ?MAXN? = ? 1001 ;
            int ?dp[MAXN][MAXN];

            int ?main()
            {
            ????
            int ?i,?j,?l,?n;
            ????
            int ?t? = ? 1 ;
            ????
            int ?tmp;
            ????
            int ?a[MAXN];
            ????
            while ?(scanf( " %d " ,? & n),?n > 0 )
            ????
            {
            ????????memset(dp,?
            0 ,? sizeof (dp));
            ????????
            for ?(i = 1 ;?i <= n;?i ++ )
            ????????????scanf(
            " %d " ,? & a[i]);
            ????????????
            ????????
            for ?(i = 1 ;?i < n;?i ++ )
            ????????????dp[i][i
            + 1 ]? = ?abs(a[i]? - ?a[i + 1 ]);
            ????????
            for ?(l = 4 ;?l <= n;?l += 2 )
            ????????
            {
            ????????????
            for ?(i = 1 ;?i <= n - l + 1 ;?i ++ )
            ????????????
            {
            ????????????????j?
            = ?i? + ?l? - ? 1 ;
            ????????????????
            if ?(a[j]? <= ?a[i + 1 ])
            ????????????????
            {
            ????????????????????tmp?
            = ?dp[i + 2 ][j]? + ?a[i]? - ?a[i + 1 ];
            ????????????????????
            if ?(dp[i][j]? < ?tmp)
            ????????????????????????dp[i][j]?
            = ?tmp;
            ????????????????}

            ????????????????
            if ?(a[i]? < ?a[j - 1 ])
            ????????????????
            {
            ????????????????????tmp?
            = ?dp[i][j - 2 ]? + ?a[j]? - ?a[j - 1 ];
            ????????????????????
            if ?(dp[i][j]? < ?tmp)
            ????????????????????????dp[i][j]?
            = ?tmp;
            ????????????????}

            ????????????????
            if ?(a[i]? >= ?a[j - 1 ])
            ????????????????
            {
            ????????????????????tmp?
            = ?dp[i + 1 ][j - 1 ]? + ?a[j]? - ?a[i];
            ????????????????????
            if ?(dp[i][j]? < ?tmp)
            ????????????????????????dp[i][j]?
            = ?tmp;
            ????????????????}

            ????????????????
            if ?(a[j]? > ?a[i + 1 ])
            ????????????????
            {
            ????????????????????tmp?
            = ?dp[i + 1 ][j - 1 ]? + ?a[i]? - ?a[j];
            ????????????????????
            if ?(dp[i][j]? < ?tmp)
            ????????????????????????dp[i][j]?
            = ?tmp;
            ????????????????}

            ????????????}

            ????????}

            ????????printf(
            " In?game?%d,?the?greedy?strategy?might?lose?by?as?many?as?%d?points.\n " ,?t ++ ,?dp[ 1 ][n]);
            ????}

            ????system(
            " pause " );
            ????
            return ? 0 ;
            }

            posted on 2006-08-28 16:00 閱讀(572) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            91久久精品91久久性色| 精品久久国产一区二区三区香蕉| 三级韩国一区久久二区综合| 国内精品久久久久久久影视麻豆| 亚洲精品成人网久久久久久| 亚洲中文字幕无码久久精品1| 久久久久久亚洲精品成人| 亚洲综合精品香蕉久久网97| 久久无码专区国产精品发布| 国产精品久久亚洲不卡动漫| 亚洲精品tv久久久久| 久久亚洲欧美日本精品| 久久只有这精品99| 久久精品国产91久久麻豆自制 | 久久久久久久综合狠狠综合| 久久综合九色综合网站| 国产精品熟女福利久久AV| 亚洲AV无码1区2区久久| 久久99久久成人免费播放| 亚洲精品蜜桃久久久久久| 国内精品免费久久影院| 99精品久久精品| 亚洲精品乱码久久久久久按摩 | 久久www免费人成看国产片| 狠狠色综合网站久久久久久久高清 | 久久精品成人免费国产片小草| 性高湖久久久久久久久| 亚洲人成无码网站久久99热国产 | 午夜精品久久久久久毛片| 久久93精品国产91久久综合| 91精品国产91久久久久久青草 | 久久99国产精品久久99| 亚洲乱码精品久久久久..| 一日本道伊人久久综合影| 亚洲乱码日产精品a级毛片久久| 18岁日韩内射颜射午夜久久成人| 国产精品久久国产精麻豆99网站| 久久国产精品99精品国产| 狼狼综合久久久久综合网| 久久综合88熟人妻| 精品久久久久久综合日本|