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

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋    

            題目地址 :

            http://acm.hdu.edu.cn/showproblem.php?pid=3016

            題目描述:

            Man Down

            Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
            Total Submission(s): 618    Accepted Submission(s): 197


            Problem Description
            The Game “Man Down 100 floors” is an famous and interesting game.You can enjoy the game from 
            http://hi.baidu.com/abcdxyzk/blog/item/16398781b4f2a5d1bd3e1eed.html

            We take a simplified version of this game. We have only two kinds of planks. One kind of the planks contains food and the other one contains nails. And if the man falls on the plank which contains food his energy will increase but if he falls on the plank which contains nails his energy will decrease. The man can only fall down vertically .We assume that the energy he can increase is unlimited and no borders exist on the left and the right.

            First the man has total energy 100 and stands on the topmost plank of all. Then he can choose to go left or right to fall down. If he falls down from the position (Xi,Yi),he will fall onto the nearest plank which satisfies (xl <= xi <= xr)(xl is the leftmost position of the plank and xr is the rightmost).If no planks satisfies that, the man will fall onto the floor and he finishes his mission. But if the man’s energy is below or equal to 0 , he will die and the game is Over.

            Now give you the height and position of all planks. And ask you whether the man can falls onto the floor successfully. If he can, try to calculate the maximum energy he can own when he is on the floor.(Assuming that the floor is infinite and its height is 0,and all the planks are located at different height).
             

            Input
            There are multiple test cases.

            For each test case, The first line contains one integer N (2 <= N <= 100,000) representing the number of planks.

            Then following N lines representing N planks, each line contain 4 integers (h,xl,xr,value)(h > 0, 0 < xl < xr < 100,000, -1000 <= value <= 1000), h represents the plank’s height, xl is the leftmost position of the plank and xr is the rightmost position. Value represents the energy the man will increase by( if value > 0) or decrease by( if value < 0) when he falls onto this plank.
             

            Output
            If the man can falls onto the floor successfully just output the maximum energy he can own when he is on the floor. But if the man can not fall down onto the floor anyway ,just output “-1”(not including the quote)
             

            Sample Input
            4 10 5 10 10 5 3 6 -100 4 7 11 20 2 2 1000 10
             

            Sample Output
            140
             

             /*

              題目描述:  

                      不同高度處有不同的水平板,跳到該板會(huì)有血量變化v,

                      問當(dāng)一個(gè)人從最高板開始,可以向左或者向右,

                      豎直跳到下面的板,求下落到地面的最大血量,或者-1。

                      線段樹+dp  

                      需要用線段樹查詢得到每個(gè)板的兩個(gè)端點(diǎn)下落后會(huì)到哪個(gè)板;

                      然后根據(jù)這個(gè)從最高的開始dp就可以了

                      dp[i] = max ( dp[i], dp[i^].v )  // dp[i^] 代表能走到 i 的線段 

            /* 


            /*

            Mail to   : miyubai@gamil.com

            Link      : http://www.cnblogs.com/MiYu  || http://www.shnenglu.com/MiYu

            Author By : MiYu

            Test      : 1

            Complier  : g++ mingw32-3.4.2

            Program   : HDU_3016

            Doc Name  : Man Down

            */

            //#pragma warning( disable:4789 )

            #include <iostream>

            #include <fstream>

            #include <sstream>

            #include <algorithm>

            #include <string>

            #include <set>

            #include <map>

            #include <utility>

            #include <queue>

            #include <stack>

            #include <list>

            #include <vector>

            #include <cstdio>

            #include <cstdlib>

            #include <cstring>

            #include <cmath>

            #include <ctime>

            using namespace std;

            struct seg_tree {

                int id, left, right;

                int mid () { return ( left + right )>>1; }  

            }seg[333333];

            inline void creat ( int x, int y, int rt = 1 ) {

                 seg[rt].left = x;

                 seg[rt].right = y;

                 //0 代表地面 其他的自然數(shù)代表各層的木板編號(hào)  -1 代表有多條線段覆蓋 

                 seg[rt].id = 0;                  

                 if ( x == y ) return ;

                 int mid = seg[rt].mid();

                 creat ( x, mid, rt << 1 );

                 creat ( mid + 1, y, rt << 1 | 1 );     

            }

            inline void modify ( int x, int y, int id, int rt = 1 ) {

                 //找到了線段, 直接修改ID 覆蓋掉 

                 if ( seg[rt].left == x && seg[rt].right == y ) {

                     seg[rt].id = id;

                     return;   

                 }

                 int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();

                 // 前面沒有return掉, 那么這條線段肯定是被覆蓋的, 將它的標(biāo)記下傳后標(biāo)記為-1 

                 if ( seg[rt].id != -1 ) {      

                     seg[LL].id = seg[RR].id = seg[rt].id;          

                     seg[rt].id = -1;

                 }      

                 if ( y <= mid ) modify ( x, y, id, LL ); //分段修改 

                 else if ( x > mid ) modify ( x, y, id, RR );

                 else {

                      modify ( x, mid, id, LL );

                      modify ( mid + 1, y, id, RR );     

                 }

            }

            inline int query ( int pos, int rt = 1 ) {   // 查詢 Pos 所在線段的 id  

                if ( seg[rt].id != -1 ) return seg[rt].id; //線段被覆蓋 直接返回 ID 

                int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();

                if ( pos <= mid ) return query ( pos, LL );             //分段查詢 

                else return query ( pos, RR );    

            }

            inline bool scan_d(int &num)  //整數(shù)輸入

            {

                    char in;bool IsN=false;

                    in=getchar();

                    if(in==EOF) return false;

                    while(in!='-'&&(in<'0'||in>'9')) in=getchar();

                    if(in=='-'){ IsN=true;num=0;}

                    else num=in-'0';

                    while(in=getchar(),in>='0'&&in<='9'){

                            num*=10,num+=in-'0';

                    }

                    if(IsN) num=-num;

                    return true;

            }

            struct Plank {

                   int x,y,h,v,left,right; 

                   //按高排序       

                   friend bool operator < ( const Plank &a, const Plank &b ) {

                          return a.h < b.h;

                   }

            }pk[100010];

            int dp[100010];

            int main ()

            {

                int N, M;

                creat ( 1, 100000 );

                while ( scan_d ( N ) ) {

                       M = -1;

                       for ( int i = 1; i <= N; ++ i ) {

                            scan_d ( pk[i].h );scan_d ( pk[i].x );scan_d ( pk[i].y );scan_d ( pk[i].v );

                            if ( pk[i].y > M ) M = pk[i].y;       // 記錄 區(qū)間最大值, 加速用的 

                       }

                       modify  ( 1, M, 0 );

                       sort ( pk + 1, pk + N + 1 );               // 按高排序 

                       memset ( dp, 0, sizeof ( dp ) );

                       dp[N] = 100 + pk[N].v;

                       // 自底向上 更新 線段, 記錄 每條線段 左右端點(diǎn)能到達(dá)的 線段 ID 

                       for ( int i = 1; i <= N; ++ i ) {          

                            int x = pk[i].left = query ( pk[i].x );

                            int y = pk[i].right = query ( pk[i].y );

                            modify ( pk[i].x, pk[i].y, i );

                       }

                       int res = -1;

                       //自頂向下 DP    dp[i] = max ( dp[i], dp[i^].v )  

                       // dp[i^] 代表能走到 i 的線段 

                       for ( int i = N; i >= 1; -- i ) {   

                           if ( dp[ pk[i].left ] < dp[i] + pk[ pk[i].left ].v )

                                dp[ pk[i].left ] = dp[i] + pk[ pk[i].left ].v;

                           if ( dp[ pk[i].right ] < dp[i] + pk[ pk[i].right ].v )

                                dp[ pk[i].right ] = dp[i] + pk[ pk[i].right ].v; 

                       } 

                       printf ( "%d\n",dp[0] > 0 ? dp[0] : -1 );

                }

                return 0;

            }


             

             

            Feedback

            # re: HDU 3016 HDOJ 3016 Memory Control ACM 3016 IN HDU  回復(fù)  更多評(píng)論   

            2010-10-18 19:21 by の屋
            Google前n個(gè)搜索結(jié)果都和你的相關(guān)

            # re: HDU 3016 HDOJ 3016 Man Down ACM 3016 IN HDU  回復(fù)  更多評(píng)論   

            2010-10-30 07:51 by MiYu
            表明哥 有 成 牛 的資質(zhì) =. = 嘿嘿

            # re: HDU 3016 HDOJ 3016 Man Down ACM 3016 IN HDU  回復(fù)  更多評(píng)論   

            2013-07-13 21:50 by fegnchen
            pascal 版的有嗎??
            久久se精品一区二区影院| 久久国产色AV免费看| 97久久超碰国产精品2021| 久久精品免费观看| 久久亚洲精品无码播放| 一本色道久久88精品综合| 99久久精品毛片免费播放| 久久亚洲国产中v天仙www| 亚洲欧美成人久久综合中文网 | 久久99国产精品久久| 久久精品国产清自在天天线| 国产精品久久久亚洲| 波多野结衣久久一区二区| 91超碰碰碰碰久久久久久综合| 欧洲人妻丰满av无码久久不卡| 一级做a爰片久久毛片看看| 久久大香香蕉国产| 久久久久久久91精品免费观看| 久久国产乱子伦精品免费午夜| 久久综合久久综合亚洲| 美女写真久久影院| 99999久久久久久亚洲| 色天使久久综合网天天| 久久久久亚洲AV综合波多野结衣| 好属妞这里只有精品久久| 亚洲午夜久久久久久久久电影网| 欧美激情精品久久久久久久九九九| 久久er热视频在这里精品| 性做久久久久久久| 久久综合狠狠综合久久综合88 | 久久无码人妻一区二区三区午夜 | 精品免费久久久久久久| 久久久久久无码国产精品中文字幕| 久久精品国产亚洲AV无码麻豆 | 无夜精品久久久久久| 亚洲欧美国产日韩综合久久 | 国产婷婷成人久久Av免费高清| 色婷婷综合久久久中文字幕| 久久亚洲国产精品成人AV秋霞| 欧洲性大片xxxxx久久久| 欧美午夜精品久久久久久浪潮|