• <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
            <2006年7月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217940
            • 排名 - 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
            竟然找到了,這道題我就是不會。
            好好看看樓主的代碼  回復  更多評論
              
            欧美丰满熟妇BBB久久久| 亚洲国产精品无码久久| 狠狠狠色丁香婷婷综合久久俺| 久久久噜噜噜久久熟女AA片 | 亚洲国产精品无码久久青草| 欧美午夜精品久久久久久浪潮| 中文字幕热久久久久久久| 久久精品a亚洲国产v高清不卡| 91久久国产视频| 久久久久久国产精品无码下载 | 国产精品天天影视久久综合网| 秋霞久久国产精品电影院| 久久精品国产亚洲7777| 色偷偷久久一区二区三区| 色8激情欧美成人久久综合电| 99久久国语露脸精品国产| 精品国产日韩久久亚洲| 国产亚洲成人久久| 性欧美丰满熟妇XXXX性久久久| 国产精品免费看久久久香蕉| 国内精品伊人久久久久| 久久国产精品无| 国产日韩久久久精品影院首页| 亚洲AV无码久久精品色欲| 中文成人久久久久影院免费观看 | 色青青草原桃花久久综合| 国产精品无码久久久久| 国产V亚洲V天堂无码久久久| 久久99精品国产麻豆宅宅| 综合久久一区二区三区 | 久久婷婷国产麻豆91天堂| 午夜欧美精品久久久久久久| 久久精品国产亚洲AV影院| 青青热久久国产久精品 | 日韩人妻无码精品久久免费一| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 麻豆亚洲AV永久无码精品久久| 日本久久中文字幕| 亚洲AV伊人久久青青草原| 亚洲午夜无码久久久久小说| 亚洲精品综合久久|