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

            搜索

            •  

            積分與排名

            • 積分 - 217938
            • 排名 - 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精品国产97久久久久久免费| 波多野结衣AV无码久久一区| 91精品国产高清久久久久久io| 国产精品热久久无码av| 亚洲人成网站999久久久综合| 久久夜色精品国产亚洲| 97久久天天综合色天天综合色hd| 精品久久人人爽天天玩人人妻| 伊人色综合久久天天人守人婷| 久久久久99精品成人片试看| 久久精品无码免费不卡| 无码人妻久久一区二区三区| 国产精品伊人久久伊人电影| 久久久久久久女国产乱让韩| 99久久精品久久久久久清纯| 亚洲日韩中文无码久久| 久久精品国产精品亜洲毛片| 日本强好片久久久久久AAA| 欧美日韩中文字幕久久久不卡| 996久久国产精品线观看| 久久人做人爽一区二区三区| 久久综合综合久久97色| 久久亚洲精品中文字幕| 久久国内免费视频| 午夜精品久久久久久影视777| 九九99精品久久久久久| 久久久久AV综合网成人| 亚洲乱码精品久久久久..| 亚洲中文字幕伊人久久无码| 久久99精品久久久久久9蜜桃| 久久99精品久久久久久hb无码| 亚洲第一极品精品无码久久 | 国产人久久人人人人爽| 欧美与黑人午夜性猛交久久久 | 色妞色综合久久夜夜| 亚洲国产天堂久久久久久| 久久天天日天天操综合伊人av| 999久久久免费国产精品播放|