[www.luogu.org] P1156 A trap of garbage *Solution*
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.)
Mon, 10 Aug 2015 18:49:28 +0800
Why not use Chinese?You are Chinese,and this is a Chinese website,isn't it?
Mon, 10 Aug 2015 19:38:01 +0800
Why not use Chinese?You are Chinese,and this is a Chinese website,isn't it?
Thu, 03 Sep 2015 17:06:37 +0800
@orz hhw: 妈个鸡你每天我的话复制复制有意思？
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.
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.
Wed, 29 Dec 2021 17:51:02 +0800
Wed, 29 Dec 2021 17:52:08 +0800
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
Tue, 01 Feb 2022 21:51:14 +0800
Thank you for taking the time to publish this information very useful! 토토사이트
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... 안전공원
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. 카지노사이트
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ใหม่ล่าสุด
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
Wed, 25 May 2022 16:41:07 +0800 I conceive you have noted some very interesting details , regards for the post. 먹튀검증
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. 手機配件
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. 手機回收
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]
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
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.
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
Tue, 01 Nov 2022 19:03:46 +0800
Hey, what kind of anti-spam plugin do you use for your blog.*:’;* 바카라사이트
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
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! 온라인바카라
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
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.
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.
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.
Sun, 23 Apr 2023 10:35:28 +0800
Thanks you!
Xây nhà trọn gói tại tphcm Thi cong alu Giá thi công nhà khung thép Sua nha gia re Giam sat cong trinh Xay nha gia re WinconsTue, 12 Dec 2023 16:04:48 +0800
Unlock the Financial Secrets of the Stars at idol net worth! From Hollywood icons to chart-topping musicians, our website offers an exclusive glimpse into the fortunes of celebrities.