青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0
<2010年9月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

常用鏈接

留言簿(24)

隨筆分類(332)

隨筆檔案(182)

FRIENDS

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜

MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋    

題目地址 :

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
 

 /*

  題目描述:  

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

          問當一個人從最高板開始,可以向左或者向右,

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

          線段樹+dp  

          需要用線段樹查詢得到每個板的兩個端點下落后會到哪個板;

          然后根據這個從最高的開始dp就可以了

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

/* 


/*

Mail to   : miyubai@gamil.com

Link      : http://www.cnblogs.com/MiYu  || http://m.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 代表地面 其他的自然數代表各層的木板編號  -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掉, 那么這條線段肯定是被覆蓋的, 將它的標記下傳后標記為-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)  //整數輸入

{

        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;       // 記錄 區間最大值, 加速用的 

           }

           modify  ( 1, M, 0 );

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

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

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

           // 自底向上 更新 線段, 記錄 每條線段 左右端點能到達的 線段 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  回復  更多評論   

2010-10-18 19:21 by の屋
Google前n個搜索結果都和你的相關

# re: HDU 3016 HDOJ 3016 Man Down ACM 3016 IN HDU  回復  更多評論   

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

# re: HDU 3016 HDOJ 3016 Man Down ACM 3016 IN HDU  回復  更多評論   

2013-07-13 21:50 by fegnchen
pascal 版的有嗎??
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美高清视频一区二区| 国产亚洲二区| 欧美成人免费小视频| 韩国成人精品a∨在线观看| 久久精品女人| 久久人体大胆视频| 亚洲国产毛片完整版| 亚洲激情一区二区| 欧美日韩激情小视频| 午夜精彩视频在线观看不卡| 欧美一区二区性| 亚洲欧洲日本专区| 日韩一级裸体免费视频| 国产精品视频内| 麻豆成人在线播放| 欧美日韩一区二区三区在线观看免| 中文久久精品| 欧美在线影院在线视频| 亚洲欧洲另类国产综合| 亚洲一区二区三区四区五区黄 | 美女主播一区| 欧美大学生性色视频| 亚洲欧美另类在线| 老牛国产精品一区的观看方式| 99re热精品| 欧美一区午夜精品| 一区二区久久| 久久精品一区二区三区四区 | 一区二区三区四区国产| 亚洲欧美日韩另类精品一区二区三区| 一区二区三区在线视频观看| 亚洲精品一二三区| 尤物在线精品| 亚洲欧美福利一区二区| 日韩午夜电影av| 欧美一区免费视频| 亚洲视频专区在线| 裸体女人亚洲精品一区| 欧美在线黄色| 欧美视频一区二区三区四区| 欧美成人午夜激情视频| 国产欧美一区二区三区视频| 亚洲精品视频在线播放| 亚洲动漫精品| 久久精品国产清高在天天线| 亚洲欧美日韩精品久久久久| 欧美精品videossex性护士| 久久午夜电影网| 国产精品影音先锋| 一区二区三区视频观看| 夜夜嗨一区二区| 麻豆九一精品爱看视频在线观看免费| 久久9热精品视频| 国产精品久久久久国产精品日日| 亚洲国产精品久久91精品| 伊人成人开心激情综合网| 欧美亚洲在线观看| 欧美一区二区黄| 国产精品美女主播在线观看纯欲| 一本高清dvd不卡在线观看| 亚洲精选在线观看| 欧美激情网友自拍| 亚洲裸体视频| 夜夜嗨av一区二区三区网页| 欧美激情一区二区三区四区| 亚洲国产岛国毛片在线| 亚洲精品日韩久久| 欧美精品一区二区三区久久久竹菊 | 亚洲成人在线网| 亚洲黄页一区| 欧美韩国一区| 亚洲乱码久久| 欧美一区二区福利在线| 国产一区二区三区四区三区四| 亚洲成色777777在线观看影院 | 欧美α欧美αv大片| 伊人精品在线| 你懂的网址国产 欧美| 亚洲大胆美女视频| 99视频超级精品| 欧美午夜精品久久久| 亚洲一区在线免费观看| 久久久久久久精| 亚洲国产一区二区三区a毛片 | 久久精品二区三区| 亚洲第一天堂av| 在线视频亚洲| 国产一区二区高清不卡| 免费久久99精品国产自| 日韩天堂在线视频| 欧美一区亚洲| 亚洲黄页视频免费观看| 欧美日韩一区在线| 久久国产精品电影| 日韩视频精品在线| 久久精品国产欧美激情| 亚洲日本视频| 国产欧美日韩在线播放| 免费看亚洲片| 亚洲女ⅴideoshd黑人| 免费试看一区| 亚洲欧美乱综合| 影音先锋中文字幕一区| 欧美日韩一区自拍| 久久久久久夜| 亚洲视频欧美在线| 欧美激情视频网站| 久久精品亚洲一区| 亚洲一区不卡| 最新亚洲激情| 国产主播精品| 国产精品久久国产愉拍| 久久婷婷综合激情| 亚洲欧美影音先锋| 99天天综合性| 亚洲春色另类小说| 欧美日韩国产在线看| 欧美一区二区三区男人的天堂| 亚洲日本成人女熟在线观看| 久久午夜激情| 久久成人一区二区| 亚洲综合视频1区| 亚洲精品美女久久7777777| 国产字幕视频一区二区| 国产精品女人网站| 欧美网站大全在线观看| 欧美激情女人20p| 美女诱惑一区| 久久久久九九九九| 欧美在线国产| 欧美亚洲视频在线观看| 亚洲欧美日韩在线综合| 99视频日韩| 99伊人成综合| 99热在线精品观看| 999亚洲国产精| 亚洲精品在线一区二区| 最新日韩欧美| 欧美不卡一卡二卡免费版| 久久综合网络一区二区| 久久视频这里只有精品| 久久久综合精品| 久久久蜜桃精品| 久久久久网址| 男女视频一区二区| 欧美国产日韩二区| 亚洲福利视频一区二区| 亚洲高清不卡一区| 91久久综合| 夜夜嗨av色综合久久久综合网| 国内成+人亚洲| 在线观看久久av| 136国产福利精品导航网址| 亚洲黄色三级| 一本色道精品久久一区二区三区| 一区二区三区欧美成人| 亚洲欧美日韩在线不卡| 久久99伊人| 欧美成人免费播放| 最新成人在线| 亚洲一区欧美激情| 久久久久久久久久久久久久一区| 久久免费偷拍视频| 欧美精品九九99久久| 欧美日韩国产色综合一二三四 | 免费av成人在线| 欧美精品v国产精品v日韩精品| 欧美体内she精视频在线观看| 国产精品婷婷| 极品av少妇一区二区| av成人免费观看| 欧美在线一区二区| 欧美激情一区在线| 亚洲无限av看| 美女视频网站黄色亚洲| 欧美视频中文字幕在线| 黄色成人在线免费| 一区二区三区欧美成人| 久久全国免费视频| 亚洲免费av网站| 久久电影一区| 欧美色视频一区| 精品动漫3d一区二区三区| 99精品视频网| 久久综合精品国产一区二区三区| 亚洲肉体裸体xxxx137| 校园春色综合网| 欧美日一区二区三区在线观看国产免 | 翔田千里一区二区| 欧美精品导航| 精品9999| 欧美一站二站| 99精品国产一区二区青青牛奶| 久久av免费一区| 国产精品日韩一区| 99av国产精品欲麻豆| 久热精品视频在线观看一区| 一区二区高清在线观看| 欧美精品www| 亚洲福利在线视频|