题解 P1156 【垃圾陷阱】

· · 题解

这道题可以把它想成一个背包问题，一个dp就ok了

（被这道题卡了一天的窝瑟瑟发抖，重点是最后还是找了神犇帮我看题）

嘤嘤嘤

这里井的高度就好比背包中的剩余空间，垃圾好比物重，剩余体力好比物品价值。

所以，这里dp[i][j]就代表第i个垃圾，高度为j时所剩余最大体力值。

然后就可以简单的（我花了1h）列出dp方程

dp[i][j+a[i].h] = max(dp[i][j+a[i].h],dp[i-1][j]-(a[i].t-a[i-1].t));//吃辣鸡

dp[i][j] = max(dp[i][j],dp[i-1][j]+a[i].v-(a[i].t-a[i-1].t));//不吃辣鸡

（这里a结构体表示每一个辣鸡的t丢出时间，v价值，h高度）

下面附上AC代码（我没用滚动数组，52ms貌似不慢）

/*The Bone Of My Sword*/ 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define MAXN 1005
using namespace std;
int dp[MAXN][MAXN];
int n,d;
struct r{
    int t,v,h;
}a[MAXN];
bool cmp(struct r q,struct r p){
    return q.t<p.t;
}
int ans;
int main(void){
    cin >> d >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i].t >> a[i].v >> a[i].h;
    }   memset(dp,~0x3f3f3f,sizeof(dp));
    sort(a+1,a+1+n,cmp);
    dp[0][0] = 10;
    a[0].t = 0;
    ans = -999999;
    for(int i = 1;i <= n;++ i){
        memset(dp[i],~0x3f3f3f,sizeof(dp[i]));
        for(int j = d;j >= 0;-- j){
            if(dp[i-1][j]<a[i].t-a[i-1].t)continue;
            if(j+a[i].h>=d){
                cout << a[i].t <<endl;
                return 0;
            }
            dp[i][j+a[i].h] = max(dp[i][j+a[i].h],dp[i-1][j]-(a[i].t-a[i-1].t));
            dp[i][j] = max(dp[i][j],dp[i-1][j]+a[i].v-(a[i].t-a[i-1].t));
        }
        ans=max(ans,dp[i][0]+a[i].t);
    }
    cout << ans << endl;
    return 0;
}