• <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題目
            久久久久久久亚洲精品| 国产精品熟女福利久久AV| 日韩一区二区三区视频久久| 久久精品极品盛宴观看| 久久亚洲AV无码精品色午夜 | 久久久久久av无码免费看大片| 久久久久免费视频| 精品国产青草久久久久福利| av无码久久久久不卡免费网站| 激情久久久久久久久久| 亚洲AV无码1区2区久久| 国产成人无码精品久久久久免费| 大香伊人久久精品一区二区| 欧美综合天天夜夜久久| 伊人久久大香线蕉av不卡| 亚洲嫩草影院久久精品| 久久精品国产乱子伦| 国产伊人久久| 国内精品人妻无码久久久影院 | 久久乐国产综合亚洲精品| 国产精品久久波多野结衣| 久久精品国产乱子伦| 亚洲国产日韩欧美久久| 久久精品国产亚洲沈樵| 久久久av波多野一区二区| 久久受www免费人成_看片中文| 国产三级精品久久| 国产精品久久久久jk制服| 无码人妻精品一区二区三区久久 | 日本久久中文字幕| 成人国内精品久久久久影院VR| 久久久噜噜噜久久熟女AA片| 亚洲精品无码久久一线| 欧美日韩精品久久久久| 亚洲一级Av无码毛片久久精品| 国产精品免费久久久久影院| 色综合色天天久久婷婷基地| 99久久成人18免费网站| 国产福利电影一区二区三区,免费久久久久久久精 | 亚洲av伊人久久综合密臀性色| 久久久久亚洲AV无码专区网站|