1684 垃圾陷阱
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
卡门——农夫约翰极其珍视的一条Holsteins奶牛——已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D (2 <= D <= 100)英尺。
卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间t(0
/*
可达性DP+背包DP.
o(nm∑w).
f[i][j]表示到达i高度j体力的状态是否可行.
那么如果f[i][j]为真.
则f[j+s[i].h][k]=true
f[j][k+s[i].w]=true.
判断逃出条件就是j+s[i].h>=limit.
逃不出的话倒着枚举时间找最晚可行时间.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 6001
using namespace std;
struct data{int t,w,h;}s[MAXN];
int n,m,ans,tot=10;
bool f[MAXN][MAXN];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
bool cmp(const data &x,const data &y)
{
return x.t<y.t;
}
int main()
{
m=read();n=read();
for(int i=1;i<=n;i++)
s[i].t=read(),s[i].w=read(),s[i].h=read(),tot+=s[i].w;
sort(s+1,s+n+1,cmp);
f[0][10]=true;
for(int i=1;i<=n;i++)
for(int j=m-1;j>=0;j--)
for(int k=tot;k>=s[i].t;k--)
if(f[j][k])
{
f[j+s[i].h][k]=true;
f[j][k+s[i].w]=true;
if(j+s[i].h>=m)
{
printf("%d",s[i].t);
return 0;
}
}
for(int i=tot;i>=10;i--)
for(int j=0;j<m;j++)
if(f[j][i])
{
printf("%d",i);return 0;
}
}/*
背包DP.
o(nm).
f[j]表示到达j高度最多能活多久.
那么如果它能等到食品(虽然是垃圾)
它就有生的希望(生命是最宝贵的%&&*%&$#).
我们考虑向后转移.
f[j+s[i].h]=max(f[j+s[i].h],f[j]);
f[j]+=s[i].w.
能逃出就逃出return.
f[0]是不垫垃圾情况的最优值.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 6001
using namespace std;
struct data{int t,w,h;}s[MAXN];
int n,m,ans,tot=10,f[MAXN],sum;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
bool cmp(const data &x,const data &y)
{
return x.t<y.t;
}
int main()
{
m=read();n=read();
for(int i=1;i<=n;i++)
s[i].t=read(),s[i].w=read(),s[i].h=read(),tot+=s[i].w;
sort(s+1,s+n+1,cmp);
f[0]=10;
for(int i=1;i<=n;i++)
for(int j=m-1;j>=0;j--)
{
if(f[j]>=s[i].t)
{
f[j+s[i].h]=max(f[j+s[i].h],f[j]);
f[j]+=s[i].w;
if(j+s[i].h>=m)
{
printf("%d",s[i].t);
return 0;
}
}
}
printf("%d",f[0]);
return 0;
}