卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方,它的深度为D(2<=D<=100)英尺。
卡门想把垃圾堆起来,等到堆得与井同样高时,她就能逃出井外了。另外,卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放,并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间t(0< t<=1000),以及每个垃圾堆放的高度h(1<=h<=25)和吃进该垃圾能维持生命的时间f(1<=f<=30),要求出卡门最早能逃出井外的时间,假设卡门当前体内有足够持续10小时的能量,如果卡门10小时内没有进食,卡门就将饿死。
输入格式:
第一行为2个整数,D 和 G (1 <= G <= 100),G为被投入井的垃圾的数量。
第二到第G+1行每行包括3个整数: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;
卡门吃掉她收到的第二个垃圾,使她的生命从10小时延伸到13小时;
卡门堆放第3个垃圾,height=19;
卡门堆放第4个垃圾,height=20。
先将每一个垃圾按出现时间升序排序
定义a.x为出现时间a.h为高度a.t为吃下获得的血量
f[i][j]表示前i个垃圾在到达j的高度时剩余的最大血量
显而易见开始时f[0][0]为10
枚举一个i为垃圾编号j为高度,就有:
1.吃下这个垃圾f[i][j]=max{f[i][j],f[i-1][j]-(a[i].x-a[i-1].x)+a[i].t}
初始f[i][j]为-INF,a[i].x-a[i-1].x为从上一个垃圾到这一个垃圾要经过多少时间
而且显然要当f[i-1][j]-(a[i].x-a[i-1].x)>=0时才在当前时间是存活着的才可以吃下这个垃圾,吃下这个垃圾回复的血量就是a[i].t,且这只牛很厉害可以在刚好死的时候吃下一个垃圾(+1s)
2.将这个垃圾叠起来f[i][j]=max{f[i][j],f[i-1][j-a[i].h]-a[i].x+a[i-1].x}
在这种情况中显然我们如果可以将当前垃圾放置并达到j这个高度时在当前高度减去当前垃圾的高度a[i].h,即([j-a[i].h)要有一个可以在经过(a[i].x-a[i-1].x)的时间仍然存活,当然j-a[i].h要>=0,时间为负数显然是不可能的
而且这只牛很厉害,在生命的最后一秒仍然可以堆上一个垃圾(+1s)
这时如过我们枚举的高度j达到了目标高度n(要满足血量>=0)我们就可以直接输出a[i].x
为什么呢,因为开始时我们排了一次序,且我们是以每一个垃圾为外循环进行枚举的,所以当有一个j达到了目标高度那么肯定是最优的
当我们出了最优解后就可以直接退出了
但如果没有找到最优解,那我们就重新枚举一次此时的答案ans为max{ans,f[i][j]+a[i].x}
因为在到达了的i个垃圾后我们还可以再撑f[i][j]s
这样就可以了
实验证明,其实可以不用判断是否有负数高度或血量的情况(不知是不是数据水?)
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #define INF 0x7f7f7f7f
7 using namespace std;
8 int deep,n;
9 struct node
10 {
11 int t;// 时间
12 int life;// 生命
13 int h;// 能垫的高度
14 }a[1001];
15 int comp(const node & a , const node & b)
16 {
17 return a.t<b.t;
18 }
19 int dp[1001][1001];
20 int main()
21 {
22 scanf("%d%d",&deep,&n);
23 for(int i=1;i<=n;i++)
24 scanf("%d%d%d",&a[i].t,&a[i].life,&a[i].h);
25
26 for (int i=0;i<=n;i++)
27 for (int j=0;j<=deep;j++)
28 dp[i][j]=-INF;
29
30 sort(a+1,a+n+1,comp);
31 dp[0][0]=10;
32 a[0].h=a[0].life=a[0].t=0;
33 int flag=0;
34
35 for(int i=1;i<=n;i++)
36 {
37 for(int j=0;j<=deep;j++)
38 {
39 if(dp[i-1][j]-a[i].t+a[i-1].t>=0)
40 {
41 dp[i][j]=max(dp[i][j],dp[i-1][j]-a[i].t+a[i-1].t+a[i].life);
42 }
43 if(dp[i-1][j-a[i].h]-a[i].t+a[i-1].t>=0&&j-a[i].h>=0)
44 {
45 dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].h]-a[i].t+a[i-1].t);
46 if(j==deep)
47 {
48 printf("%d",a[i].t);
49 flag=1;
50 return 0;
51 }
52 }
53 }
54 }
55 int ans=0;
56 if(flag==0)
57 {
58 for(int i=0;i<=n;i++)
59 {
60 for(int j=0;j<=deep;j++)
61 {
62 if(dp[i][j]!=INF)
63 ans=max(ans,dp[i][j]+a[i].t);
64 }
65 }
66 }
67
68 printf("%d",ans);
69 return 0;
70 }