• <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)

            相冊(cè)

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217940
            • 排名 - 117

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            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) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM題目
            亚洲午夜无码久久久久| 99久久综合国产精品二区| 日韩精品久久久久久久电影| 久久综合久久综合九色| 亚洲伊人久久大香线蕉苏妲己| 狠狠色丁香婷婷久久综合不卡| 天天综合久久久网| 欧美黑人激情性久久| 久久精品国产免费| 国产欧美久久久精品影院| www.久久99| 漂亮人妻被中出中文字幕久久| 国产韩国精品一区二区三区久久| 久久99精品久久久久久水蜜桃| 无码人妻精品一区二区三区久久 | 日韩AV毛片精品久久久| 中文字幕久久精品无码| 久久美女网站免费| 久久人与动人物a级毛片| 国产精品9999久久久久| 伊人久久大香线蕉无码麻豆| 亚洲综合精品香蕉久久网97| 久久婷婷五月综合成人D啪| 国产精品VIDEOSSEX久久发布| 久久婷婷成人综合色综合| 中文字幕亚洲综合久久菠萝蜜| 热99re久久国超精品首页| 久久99热只有频精品8| 久久99热这里只有精品国产| 久久久精品视频免费观看| 99久久精品国产毛片| 久久亚洲国产欧洲精品一| 99久久99久久久精品齐齐| 久久国产精品成人影院| 国产偷久久久精品专区| 尹人香蕉久久99天天拍| 亚洲国产成人久久综合碰| 亚洲欧洲精品成人久久奇米网| 久久伊人中文无码| 久久国产AVJUST麻豆| 色青青草原桃花久久综合|