题目描述
卡门――农夫约翰极其珍视的一条 Holsteins 奶牛――已经落了到 "垃圾井" 中."垃圾井" 是农夫们扔垃圾的地方, 它的深度为 \(D(2 \le D \le 100)\) 英尺.
卡门想把垃圾堆起来, 等到堆得与井同样高时, 她就能逃出井外了. 另外, 卡门可以通过吃一些垃圾来维持自己的生命.
每个垃圾都可以用来吃或堆放, 并且堆放垃圾不用花费卡门的时间.
假设卡门预先知道了每个垃圾扔下的时间 \(t(0<t \le 1000)\), 以及每个垃圾堆放的高度 \(h(1 \le h \le 25)\) 和吃进该垃圾能维持生命的时间 \(f(1 \le f \le 30)\), 要求出卡门最早能逃出井外的时间, 假设卡门当前体内有足够持续 \(10\) 小时的能量, 如果卡门 \(10\) 时内没有进食, 卡门就将饿死.
输入格式
第一行为 \(2\) 个整数,\(D\) 和 \(G (1 \le G \le 100)\),\(G\) 为被投入井的垃圾的数量.
第二到第 \(G+1\) 行每行包括 \(3\) 个整数:\(T (0 < T <= 1000)\), 表示垃圾被投进井中的时间;\(F (1 \le F \le 30)\), 表示该垃圾能维持卡门生命的时间; 和 \(H (1 \le H \le 25)\), 该垃圾能垫高的高度.
输出格式
如果卡门可以爬出陷阱, 输出一个整数表示最早什么时候可以爬出; 否则输出卡门最长可以存活多长时间.
输入输出样例
输入 #1
- 20 4
- 5 4 9
- 9 3 2
- 12 6 10
- 13 1 1
输出 #1
13
说明 / 提示
[样例说明]
卡门堆放她收到的第一个垃圾:\(height=9\);
卡门吃掉她收到的第 \(2\) 个垃圾, 使她的生命从 \(10\) 时延伸到 \(13\) 时;
卡门堆放第 \(3\) 个垃圾,\(height=19\);
卡门堆放第 \(4\) 个垃圾,\(height=20\).
对于每个垃圾, 我们有两种处理方法: 吃掉或者垫起来.
这透露出浓浓的背包气息. 考虑 \(dp\).
对于整个题来讲, 我们有 \(4\) 个变量: 当前时间 / 垃圾的编号 / 当前高度 / 当前生命.
这样空间开不下, 但是我们容易观察到对于每个垃圾, 没有必要留着而应该直接使用, 所以当前时间可以和垃圾的编号合并.
这样只有了 \(3\) 个变量. 题目里面要求求出达到高度 \(d\) 的最短时间, 所以我们用 \(dp[i][j]\) 表示当降下第 \(i\) 道垃圾且处理完这个垃圾之后的生命为 \(j\) 时, 最大可以到达的高度. 原题里面很多题解都是用 \(dp[i][j]\) 表示最大生命, 不知道为什么.
请注意这里的生命是从 \(0\) 时刻开始能够存活的总生命值. 也就是说这个生命不会递减只会增加, 判断死亡的标准是当前的生命值小于当前时间点.
对于每个垃圾, 我们有两种选择:
第一, 利用它提升高度. 那么 \(dp[i][j]=dp[i-1][j]+h[i]\), 表示第 \(i\) 个垃圾被用来提升了 \(h[i]\) 的高度.
第二, 利用它回复生命. 那么 \(dp[i][j]=dp[i-1][j-f[i]]\), 表示第 \(i\) 个垃圾被用来回复了 \(f[i]\) 的生命.
当我们第一次找到了 \(dp[i][j]\geq d\), 则输出 \(t[i]\) 之后 \(return 0\), 因为垃圾是按照时间顺序枚举的.
如果找不到满足要求的答案, 说明无法跳出. 这时我们的判断策略有变化, 因为要尽可能活下去, 也就是说应该用所有的垃圾回复生命. 所以对于每一个垃圾落下的时间, 我们发现它大于当前的生命值则输出当前生命值并结束; 否则生命值加上这个垃圾的回复量.
注意事项有三点:
第一, 如果利用垃圾回复生命, 必须判断 \(j-f[i]\geq t[i]\), 因为 \(dp[i][j]\) 的第二维表示的是处理完这个垃圾之后的生命, 我们必须判断原来的生命能不能坚持到这个时间点. 判断的方法如上, 因为生命值的定义是从 \(0\) 开始能坚持多长时间, 与时间的增长等速同向. 忘记这个点会丢失 \(10-30pts\).
第二, 请记得给输入按时间排序. 题目中没有表示所有圣诫之光按照时间给出, 忘记这个点会丢失 \(20pts\).
第三, 请记得初始化 \(dp\) 数组为 \(-inf\). 因为如 \(dp[0][9]\) 之类的状态走不到.
上代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cctype>
- #include<cmath>
- #define int long long
- #define rep(i,a,n) for(register int i=a;i<=n;++i)
- #define dwn(i,n,a) for(register int i=n;i>=a;--i)
- using namespace std;
- int d,g,t[100050],f[100050],h[100050],dp[105][3050];
- struct rub
- {
- int t,f,h;
- }a[100050];
- inline int read()
- {
- int x=0,f=1;
- char ch=getchar();
- while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
- while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
- return x*f;
- }
- void write(int x)
- {
- if(x<0)putchar('-'),x=-x;
- if(x==0)return;
- write(x/10);
- putchar(x%10+'0');
- }
- bool cmp(rub a,rub b)
- {
- if(a.t==b.t)
- {
- if(a.f==b.f)return a.h<b.h;
- else return a.f<b.f;
- }
- return a.t<b.t;
- }
- signed main()
- {
- d=read(),g=read();
- rep(i,1,g)a[i].t=read(),a[i].f=read(),a[i].h=read();
- sort(a+1,a+g+1,cmp);
- memset(dp,128,sizeof dp);
- dp[0][10]=0;
- rep(i,1,g)
- {
- rep(j,max(a[i].t,a[i].f),a[g].t+1)
- {
- dp[i][j]=dp[i-1][j]+a[i].h;
- if(j-a[i].f>=a[i].t)dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].f]);
- // printf("%lld %lld %lld\n",i,j,dp[i][j]);
- if(dp[i][j]>=d)
- {
- write(a[i].t);
- return 0;
- }
- }
- }
- int last=10;
- a[g+1].t=0x3f3f3f3f;
- rep(i,1,g+1)
- {
- if(last<a[i].t)
- {
- write(last);
- return 0;
- }
- last+=a[i].f;
- }
- return 0;
- }
- /*
- 6 5
- 10 30 5
- 40 30 5
- 70 30 5
- 100 30 5
- 130 2 5
- */
来源: https://www.cnblogs.com/qxds/p/11962199.html