• <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
            <2005年12月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217924
            • 排名 - 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題目
            97精品伊人久久久大香线蕉| 99精品久久久久中文字幕| 91久久精品无码一区二区毛片| 精品999久久久久久中文字幕| 国产成人精品久久免费动漫| 国产精品久久久久久久午夜片| 亚洲国产精品综合久久一线| 久久ww精品w免费人成| 国产精品免费久久久久电影网| 久久久这里有精品中文字幕| 久久影院综合精品| 久久精品国产亚洲5555| 日韩乱码人妻无码中文字幕久久| 国产三级精品久久| 久久国产热精品波多野结衣AV | 久久综合久久伊人| 东京热TOKYO综合久久精品| 久久夜色精品国产| 久久电影网2021| 人妻精品久久久久中文字幕一冢本| 久久精品国产清自在天天线| 99久久久国产精品免费无卡顿| 久久99精品久久久久久9蜜桃| 亚洲成色WWW久久网站| 一97日本道伊人久久综合影院| 狠色狠色狠狠色综合久久| 综合人妻久久一区二区精品| 久久综合色之久久综合| 精品视频久久久久| 亚洲一区二区三区日本久久九| 男女久久久国产一区二区三区| 久久免费看黄a级毛片| 久久精品国产男包| 蜜桃麻豆WWW久久囤产精品| 日韩久久久久中文字幕人妻| 久久久久婷婷| 亚洲精品tv久久久久| 久久久久亚洲精品男人的天堂| 国产毛片久久久久久国产毛片| 一本久久a久久精品综合夜夜| 久久亚洲精品中文字幕|