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

酱油 posted @ Sun, 09 Aug 2015 20:53:46 +0800 in OI life with tags solution , 733 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: 妈个鸡你每天我的话复制复制有意思?


Login *


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