题解 P1156 【垃圾陷阱】

· · 题解

应该看得出就是一个背包吧！把垃圾的高度看成物重，能增加的生命的长短看成价值，

然后把井的高度看成包的大小，要求必须把包填满（或爆）能取得的最小价值【手动滑稽】。

直接搞一个背包：

设dp[i][j]表示前i个垃圾（注意一定要先按垃圾出现时间排序好），到达高度j时所拥有的最长的生命时间。

那么dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i].v-(a[i].t-a[i-1].t))（吃，不填）

dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].h]-(a[i].t-a[i-1].t))（不吃，填）

如果有一个dp[i][j]>=0且j+a[i].h>=D，那么就走出去了，

不然就是在dp[i][0]+a[i].t中取个最大值就好了。

至于刷表法，还是填表法，就看个人喜好了。

搞一个滚动数组优化一下空间（其实没必要，弄不好还搞错了）。

参考代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int M=1010;
struct Rubbish{
    int t,v,h;
    bool operator < (const Rubbish &rhs) const {
        return t<rhs.t;
    }
}a[M];
int dp[2][M],n,m;
int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
int main(){
    m=read(),n=read();
    for (int i=1;i<=n;i++)
        a[i].t=read(),a[i].v=read(),a[i].h=read();
    sort(a+1,a+n+1);
    memset(dp,~0x3f,sizeof(dp));
    dp[0][0]=10;a[0].t=0;
    int res=-INF;
    for (int i=1;i<=n;i++){
        int cur=i&1,pre=cur^1;
        memset(dp[cur],~0x3f,sizeof(dp[cur]));
        for (int j=m;j>=0;j--){
            if (dp[pre][j]<a[i].t-a[i-1].t)continue;
            if (j+a[i].h>=m){
                printf("%d",a[i].t);
                return 0;
            }
            dp[cur][j+a[i].h]=max(dp[cur][j+a[i].h],dp[pre][j]-(a[i].t-a[i-1].t));
            dp[cur][j]=max(dp[pre][j]+a[i].v-(a[i].t-a[i-1].t),dp[cur][j]);
        }
        res=max(res,dp[cur][0]+a[i].t);
    }
    printf("%d",res);
    return 0;
}