[www.luogu.org] P1156 A trap of garbage *Solution*

酱油 posted @ Sun, 09 Aug 2015 20:53:46 +0800 in OI life with tags solution , 1538 readers

A DP problem (Estimated Difficulty: Junior, NOIP)

"Sky Gate":http://www.luogu.org/problem/show?pid=1156

A cow fell into a trap of garbage, whose depth is D(meter(s)), and is now at the bottom (Height=0).
He could get out of the trap when his position is more than D(meter(s)) in height.
There are farmers throwing G pieces of garbage into the trap in total. The cow will choose either to put the garbage below him and rise up himself in height, or to swallow the garbage and get more time surviving in the trap.
Now we know the time farmers throw any piece of garbage, the height of any piece of garbage, and its ability to feed the cow.
The cow can struggle to live with an initial living time of 10(hours). Then when will he get out the trap?
  
Input: 
D G
T_i F_i H_i (1<=i<=G, indicating the time of throwing down the piece of garbage, its ability to feed the cow and its height)
Output:
t(indicating the least time the cow can get out of the trap, if and only if he is able to get out and won't die of hunger;
or indicating the longest time the cow will survive in the trap, if and only if he is not able to get out any longer)
Sample Input:
20 4
5 4 9
9 3 2
12 6 10
13 1 1
Sample Output:
13
Explanations:
The cow could choose to put Garbage No.1, 3, and 4 below him and get a height of 9+10+1=20 to get out of the trap.
And of course, he should eat up Garbage No.2 to make himself survive 3 more hours.

For all 11 testcases: 1<=D,G<=100; 1<=T_i<=1000, 1<=F_i<=30, 1<=H_i<=25 (1<=i<=G)

A typical DP problem with more than one solution, for its very little data. I simply show the easiest way to solve it here.

First of all, it is very important to sort all the pieces of garbage by the time it would be thrown down.

Suppose f[i] indicates the longest surviving time at the height of i:

for j->1 to G; for i->D to 0;

f[i+h[j]]=max(f[i+H[j]],f[i]);f[i]+=F[i];

 

If the depth can be reached, print the current time T[i] immediately, or we could print the value of f[0], indicating the longest surviving time (The pity cow eats every piece of garbage and will die at the bottom of the trap in despair T_T)

    #include <iostream>  
    #include <algorithm>  
    #include <cstdio>  
    #include <cstdlib>  
    #include <cmath>  
    #include <ctime>  
    #include <cstring>  
    #define DONS 1010  
    using namespace std;  
    int d,g,i,j,k,t[DONS],f[DONS],h[DONS],temt[DONS],temf[DONS],temh[DONS],dp[DONS];  
    void merge(int l,int r,int ll,int rr)  
    {  
        int i=l,j=r,ii=ll,jj=rr,x=0;  
        while(i<=r&&ii<=rr)  
        {  
            if(t[i]<t[ii]){x++;temt[x]=t[i];temf[x]=f[i];temh[x]=h[i];i++;}  
            else{x++;temt[x]=t[ii];temf[x]=f[ii];temh[x]=h[ii];ii++;}  
        }  
        while(i<=r){x++;temt[x]=t[i];temf[x]=f[i];temh[x]=h[i];i++;}  
        while(ii<=rr){x++;temt[x]=t[ii];temf[x]=f[ii];temh[x]=h[ii];ii++;}  
        for(j=1;j<=x;j++){t[l+j-1]=temt[j];f[l+j-1]=temf[j];h[l+j-1]=temh[j];}  
    }  
    void mergesort(int l,int r)  
    {  
        if(l>=r)return;  
        mergesort(l,(l+r)>>1);mergesort(((l+r)>>1)+1,r);  
        merge(l,(l+r)>>1,((l+r)>>1)+1,r);  
    }  
    int main()  
    {  
        scanf("%d%d",&d,&g);for(i=1;i<=g;i++)scanf("%d%d%d",&t[i],&f[i],&h[i]);  
        mergesort(1,g);dp[0]=10;  
        for(i=1;i<=g;i++)  
        for(j=d;j>=0;j--)if(dp[j]>=t[i])  
        {dp[j+h[i]]=max(dp[j],dp[j+h[i]]);dp[j]+=f[i];  
        if(j+h[i]>=d){printf("%d\n",t[i]);return 0;}}  
        printf("%d\n",dp[0]);  
        return 0;         
    }  

 

And that's it. Not very difficult, right?

 

If you have better solution, please show your solution through comments, and I'll take it seriously.

(Comments are welcomed and it is recommended that you reply in English.)

Avatar_small
hhw said:
Mon, 10 Aug 2015 18:49:28 +0800

Why not use Chinese?You are Chinese,and this is a Chinese website,isn't it?

Avatar_small
orz hhw said:
Mon, 10 Aug 2015 19:38:01 +0800

Why not use Chinese?You are Chinese,and this is a Chinese website,isn't it?

Avatar_small
hhw said:
Thu, 03 Sep 2015 17:06:37 +0800

@orz hhw: 妈个鸡你每天我的话复制复制有意思?

Avatar_small
Whitefield Escorts S said:
Tue, 21 Dec 2021 17:24:18 +0800

The solution for this is quite working and will be helping in the day to day life.

Avatar_small
Escorts in Domlur said:
Tue, 21 Dec 2021 17:25:34 +0800

It will be one of the best websites if you will be going to make a change out of this.

Avatar_small
Aditi said:
Wed, 29 Dec 2021 17:52:08 +0800
I can set up my basic idea from this post. It gives all around information. A responsibility of appreciation is all together for this basic information for all,..

 

Avatar_small
Jaipur Escorts Servi said:
Tue, 18 Jan 2022 17:39:08 +0800

I as of late went over your blog and have been perusing along. I figured I would leave my first remark. I don't have the foggiest idea what to say aside from that I have appreciated perusing. Decent blog. I will continue to visit this blog all the time

Avatar_small
AAA said:
Tue, 01 Feb 2022 21:51:14 +0800

Thank you for taking the time to publish this information very useful! 토토사이트

Avatar_small
AAA said:
Tue, 08 Feb 2022 19:31:50 +0800

I like your post. It is good to see you verbalize from the heart and clarity on this important subject can be easily observed... 안전공원

Avatar_small
AAA said:
Mon, 21 Feb 2022 03:01:20 +0800

Very useful post. I think this can make me some idea. And i wish there was a post about wireless phone plans. 카지노사이트

Avatar_small
AAA said:
Mon, 21 Mar 2022 04:17:30 +0800

Your work is very good and I appreciate you and hopping for some more informative posts. Thank you for sharing great information to us. เกมสล็อต ค่าย pgใหม่ล่าสุด

Avatar_small
AAA said:
Sat, 26 Mar 2022 20:11:50 +0800

Your blog is amazing dude” i love to visit it everyday. very nice layout and content ,     TeleMental Health Services

Avatar_small
AAA said:
Wed, 25 May 2022 16:41:07 +0800 I conceive you have noted some very interesting details , regards for the post. 먹튀검증
Avatar_small
AAA said:
Fri, 03 Jun 2022 23:36:50 +0800

I together with my buddies were found to be analyzing the great key points from your website while suddenly got a horrible suspicion I had not thanked the blog owner for those secrets. These boys were definitely consequently happy to read through all of them and have in effect extremely been using these things. Appreciate your really being well accommodating and then for obtaining such terrific useful guides most people are really wanting to learn about. Our own sincere regret for not saying thanks to you sooner. 手機配件

Avatar_small
AAA said:
Sun, 12 Jun 2022 22:22:05 +0800

I?¦m now not sure where you are getting your information, however great topic. I needs to spend some time finding out more or understanding more. Thanks for great information I used to be looking for this info for my mission. 手機回收

Avatar_small
Anamika said:
Tue, 14 Jun 2022 15:29:11 +0800

This is thoroughly overpowering. I'm no doubt particularly astoundingly in wide speak around satisfied to the point which you have shared this focal electronic magazine post. Keep on posting

[url=https://www.thebangaloreescorts.in/escorts/agartala.html]Agartala Escorts[/url]
[url=https://www.thebangaloreescorts.in/escorts/ajmer.html]Escorts in Ajmer[/url]
[url=https://www.thebangaloreescorts.in/escorts/akola.html]Akola Escorts Service[/url]
[url=https://www.thebangaloreescorts.in/escorts/ambattur.html]Escorts Service in Ambattur[/url]
[url=https://www.thebangaloreescorts.in/escorts/amravati.html]Amravati Escorts Agency[/url]

Avatar_small
qqhow said:
Wed, 22 Jun 2022 00:31:29 +0800

Youre so cool! I dont suppose Ive read anything similar to this prior to. So nice to uncover somebody with some original thoughts on this subject. realy appreciation for beginning this up. this web site is one area that is needed on the internet, somebody if we do originality. beneficial job for bringing new stuff for the web! slotxo

 

=========================

 

What i do not realize is actually how you’re not really much more well-liked than you might be right now. You are so intelligent. You realize thus considerably relating to this subject, made me personally consider it from so many varied angles. Its like women and men aren’t fascinated unless it’s one thing to do with Lady gaga! Your own stuffs nice. Always maintain it up! joker123

Avatar_small
unf library said:
Sat, 20 Aug 2022 02:30:47 +0800

The Carpenter Library aspires to be the intellectual center of its community, to foster innovations that lead to the discovery of knowledge,unf library and to further 2021. The Carpenter Library aspires to be the intellectual center of its community, to foster innovations that lead to the discovery of knowledge, and to further 2021.

Avatar_small
meidir said:
Sun, 02 Oct 2022 00:32:26 +0800 I very delighted to find this web site on bing, just what I was looking for besides saved to bookmarks . Macbook pro
Avatar_small
meidir said:
Tue, 01 Nov 2022 19:03:46 +0800

Hey, what kind of anti-spam plugin do you use for your blog.*:’;* 바카라사이트

Avatar_small
meidir said:
Mon, 14 Nov 2022 01:03:16 +0800

Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!Thanks online quran kids

Avatar_small
meidir said:
Fri, 18 Nov 2022 20:57:24 +0800

Great site. Lots of useful info here. I’m sending it to several friends ans also sharing in delicious. And obviously, thanks for your sweat! 온라인바카라

Avatar_small
Prostitute Service i said:
Sat, 17 Dec 2022 13:15:37 +0800

I like this substance about the human piece and I will correspondingly give a design on this shocking point

Avatar_small
Bangalore Five Star said:
Sat, 17 Dec 2022 13:16:21 +0800

Astonishing article and an incomprehensibly overpowering made! I like your blog and I read it continually. Appreciation for proposing to us.

Avatar_small
Hotel Leela Palace E said:
Sat, 17 Dec 2022 13:16:51 +0800

Here I first visit here. I found a lot of overpowering stuff concerning your blog, particularly its conversation.

Avatar_small
Hotel Radisson Blu E said:
Sat, 17 Dec 2022 13:17:22 +0800

The substance is conspicuous! I love looking at regions that are stacked with data and hypnotizing stories. All that thought regarding freed from a couple of new obliging data when I read one.


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter