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

            搜索

            •  

            積分與排名

            • 積分 - 217899
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            Spiderman’s workout
            Time Limit:1000MS? Memory Limit:65536K
            Total Submit:211 Accepted:63 Special Judged

            Description
            Staying fit is important for every super hero, and Spiderman is no exception. Every day he undertakes a climbing exercise in which he climbs a certain distance, rests for a minute, then climbs again, rests again, and so on. The exercise is described by a sequence of distances d1, d2, . . . , dm telling how many meters he is to climb before the first first break, before the second break, and so on. Froman exercise perspective it does not really matter if he climbs up or down at the i:th climbing stage, but it is practical to sometimes climb up and sometimes climb down so that he both starts and finishes at street level. Obviously, he can never be below street level. Also, he would like to use as low a building as possible (he does not like to admit it, but he is actually afraid of heights). The building must be at least 2 meters higher than the highest point his feet reach during the workout.

            He wants your help in determining when he should go up and when he should go down. The answer must be legal: it must start and end at street level (0 meters above ground) and it may never go below street level. Among the legal solutions he wants one that minimizes the required building height. When looking for a solution, you may not reorder the distances.

            If the distances are 20 20 20 20 he can either climb up, up, down, down or up, down, up, down. Both are legal, but the second one is better (in fact optimal) because it only requires a building of height 22, whereas the first one requires a building of height 42. If the distances are 3 2 5 3 1 2, an optimal legal solution is to go up, up, down, up, down, down. Note that for some distance sequences there is no legal solution at all (e.g., for 3 4 2 1 6 4 5).

            Input
            The first line of the input contains an integer N giving the number of test scenarios. The following 2N lines specify the test scenarios, two lines per scenario: the first line gives a positive integer M ≤ 40 which is the number of distances, and the following line contains the M positive integer distances. For any scenario, the total distance climbed (the sum of the distances in that scenario) is at most 1000.

            Output
            For each input scenario a single line should be output. This line should either be the string "IMPOSSIBLE" if no legal solution exists, or it should be a string of length M containing only the characters "U" and "D", where the i:th character indicates if Spiderman should climb up or down at the i:th stage. If there are several different legal and optimal solutions, output one of them (it does not matter which one as long as it is optimal).

            Sample Input

            3
            4
            20 20 20 20
            6
            3 2 5 3 1 2
            7
            3 4 2 1 6 4 5

            Sample Output

            UDUD
            UUDUDD
            IMPOSSIBLE

            Source
            Svenskt M?sterskap i Programmering 2003

            ghost_wei說十分鐘就能打完, 汗, 牛人。。

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

            const ? int ?MAXN? = ? 2001 ;
            const ? int ?INF? = ? 2000000000 ;
            int ?dp[ 41 ][MAXN];
            int ?s[ 41 ][MAXN];
            int ?a[ 41 ];

            void ?print( int ?n,? int ?m)
            {
            ????
            if ?(n? == ? 0 )?
            ????????
            return ?;

            ????
            if ?(s[n][m]? == ? 0 )
            ????
            {
            ????????print(n
            - 1 ,?m - a[n]);
            ????????printf(
            " U " );
            ????}

            ????
            else
            ????
            {
            ????????print(n
            - 1 ,?m + a[n]);
            ????????printf(
            " D " );
            ????}

            }


            void ?solve()
            {
            ????
            int ?n;
            ????
            int ?i,?j;
            ????
            int ?t1,?t2;
            ????
            int ?maxn? = ? 0 ;

            ????scanf(
            " %d " ,? & n);
            ????
            for ?(i = 1 ;?i <= n;?i ++ )
            ????
            {
            ????????scanf(
            " %d " ,? & a[i]);
            ????????maxn?
            += ?a[i];
            ????}


            ????memset(dp,?
            - 1 ,? sizeof (dp));
            ????memset(s,?
            - 1 ,? sizeof (s));

            ????dp[
            1 ][a[ 1 ]]? = ?a[ 1 ];
            ????s[
            1 ][a[ 1 ]]? = ? 0 ;

            ????
            for ?(i = 2 ;?i <= n;?i ++ )
            ????
            {
            ????????
            for ?(j = 0 ;?j < maxn;?j ++ )
            ????????
            {
            ????????????t1?
            = ?INF;
            ????????????t2?
            = ?INF;
            ????????????
            if ?(j - a[i]? >= ? 0 ? && ?dp[i - 1 ][j - a[i]]? != ? - 1 )
            ????????????????t1?
            = ?max(j,?dp[i - 1 ][j - a[i]]);
            ????????????
            if ?(j + a[i]? < ?maxn? && ?dp[i - 1 ][j + a[i]]? != ? - 1 )
            ????????????????t2?
            = ?max(j,?dp[i - 1 ][j + a[i]]);
            ????????????
            if ?(t1? < ?t2)
            ????????????
            {
            ????????????????dp[i][j]?
            = ?t1;
            ????????????????s[i][j]?
            = ? 0 ;
            ????????????}

            ????????????
            else
            ????????????
            {
            ????????????????
            if ?(t2? != ?INF)
            ????????????????
            {
            ????????????????????dp[i][j]?
            = ?t2;
            ????????????????????s[i][j]?
            = ? 1 ;
            ????????????????}

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

            ????????}

            ????}

            ????
            if ?(dp[n][ 0 ]? == ? - 1 )
            ????????printf(
            " IMPOSSIBLE\n " );
            ????
            else
            ????
            {
            ????????print(n,?
            0 );
            ????????printf(
            " \n " );
            ????}

            }


            int ?main()
            {
            ????
            int ?caseTime;

            ????scanf(
            " %d " ,? & caseTime);
            ????
            while ?(caseTime -- ? != ? 0 )
            ????
            {
            ????????solve();
            ????}

            ????
            return ? 0 ;
            }
            posted on 2006-09-09 20:06 閱讀(458) 評論(1)  編輯 收藏 引用 所屬分類: ACM題目

            FeedBack:
            # re: pku(3003, 枚舉高度的dp)  2006-11-06 21:41 bmexue
            竟然找到了,這道題我就是不會。
            好好看看樓主的代碼  回復  更多評論
              
            91久久精品91久久性色| AV色综合久久天堂AV色综合在 | 麻豆成人久久精品二区三区免费| 亚洲国产精品无码久久青草| 精品久久人人妻人人做精品| 久久人人爽人人澡人人高潮AV| 污污内射久久一区二区欧美日韩| 国产精品久久久久久久久久影院 | 人妻少妇久久中文字幕一区二区 | 人人狠狠综合久久亚洲88| 亚洲午夜久久久精品影院| 久久亚洲sm情趣捆绑调教| 久久精品国产亚洲AV香蕉| 伊人久久大香线蕉综合网站| 性欧美大战久久久久久久久| 免费一级做a爰片久久毛片潮| 亚洲精品乱码久久久久久久久久久久 | 亚洲日韩中文无码久久| 久久www免费人成看国产片| 亚洲精品国产美女久久久| 色综合久久88色综合天天 | 国产成人精品久久免费动漫| 伊人色综合久久天天人手人婷| 九九99精品久久久久久| 国产精品岛国久久久久| 色播久久人人爽人人爽人人片AV| 久久99亚洲综合精品首页| 久久久久久毛片免费播放| 777午夜精品久久av蜜臀| 亚洲国产精品综合久久一线| 91久久精品无码一区二区毛片| 国产午夜精品久久久久免费视| 东方aⅴ免费观看久久av| 久久精品亚洲福利| 亚洲精品久久久www| 精品久久久无码中文字幕天天 | 国产精品18久久久久久vr| 久久亚洲精品成人AV| 伊人久久大香线蕉亚洲五月天 | 少妇精品久久久一区二区三区| 国产精品久久久久久五月尺|