岩石谷 - P1156 垃圾收集器 [背包类]
题目描述
卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方,它的深度为 D(2≤D≤100)D(2 \le D \le 100)D(2≤D≤100) 英尺。
卡门想把垃圾堆起来,等到堆得与井同样高时,她就能逃出井外了。另外,卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放,并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间 t (0<t≤1000)(0< t \le 1000)(0<t≤1000),以及每个垃圾堆放的高度h(1≤h≤25)h(1 \le h \le 25)h(1≤h≤25)和吃进该垃圾能维持生命的时间f(1≤f≤30)f(1 \le f \le 30)f(1≤f≤30),要求出卡门最早能逃出井外的时间,假设卡门当前体内有足够持续10小时的能量,如果卡门10小时内没有进食,卡门就将饿死。
输入格式:
第一行为2个整数,D和G(1≤G≤100)D和 G (1 \le G \le 100)D和G(1≤G≤100),G为被投入井的垃圾的数量。
第二到第G+1行每行包括33个整数:T(0<T<=1000),表示垃圾被投进井中的时间;F(1≤F≤30),表示该垃圾能维持卡门生命的时间;和 H(1≤H≤25),该垃圾能垫高的高度。
输出格式:
如果卡门可以爬出陷阱,输出一个整表示最早什么时候可以爬出;否则输出卡门最长可以存活多长时间。
输入样例#1:
20 4
5 4 9
9 3 2
12 6 10
13 1 1
输出样例#1:
13
说明
[样例说明]
卡门堆放她收到的第一个垃圾:height=9;
卡门吃掉她收到的第22个垃圾,使她的生命从10小时延伸到13小时;
卡门堆放第33个垃圾,height=19;
卡门堆放第44个垃圾,height=20。
思路 : 看到这道题总感觉很熟悉,可是一做又做不出来,明知道是背包就是做不出来,后来万恶的看了题解,我觉得用这道题彻底理解背包挺好的,这次理解的不是背包的思想,而是理解背包的具体codeing方法
开一个dp数组用dp[i]来维护当 i 为高度的时候最大的时间
AC code :
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 110 ;
int dp[maxn] , d ,g ;
struct node {
int time ,lenght ,hight ;
}ss[1005];
int cmp (node x,node y) {
return x.time < y.time ;
}
int main() {
scanf("%d %d",&d, &g ) ;
for (int i = 1 ; i <= g ; i ++ ) {
scanf("%d %d %d",&ss[i].time ,&ss[i].lenght ,&ss[i].hight ) ;
}
sort( ss + 1 , ss + g + 1 , cmp ) ;
memset(dp ,0 ,sizeof(dp) ) ;
dp[0] = 10 ;
for (int i = 1 ; i <= g ; i ++ ) {
for (int j = d ; j >= 0 ; j -- ) {
if ( dp[j] >= ss[i].time ) {
if ( j + ss[i].hight >= d ) {
printf("%d\n",ss[i].time ) ;
return 0;
}
dp[j + ss[i].hight] = max(dp[j] ,dp[j + ss[i].hight] ) ;
dp[j] += ss[i].lenght ;
}
}
}
printf("%d\n",dp[0] ) ;
return 0;
}