[Luogu] P1156 垃圾陷阱

题目描述

卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D(2≤D≤100)英尺。

卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。

每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。

假设卡门预先知道了每个垃圾扔下的时间t(0<t≤1000)，以及每个垃圾堆放的高度h(1≤h≤25)和吃进该垃圾能维持生命的时间f(1≤f≤30)，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。

题目解析

设状态dp[第i个垃圾][还有j的能量][吃/不吃] = 最大高度。

也许可以压缩到1维。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 100 + 5;
const int MAXM = 1000 + 5;
const int INF = 0x3f3f3f3f;

struct Holsteins {
    int x,y,z;
    friend bool operator < (Holsteins fir,Holsteins sec) {
        return fir.x < sec.x;
    }
} a[MAXN];

int n,h;
int tot,last,tothigh;
int dp[MAXN][MAXM][2];

inline int rd() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main() {
    scanf("%d%d",&h,&n);
    int x,y,z;
    last = 0;
    memset(dp,~0x3f,sizeof(dp));
    dp[0][10][0] = 0;
    tot = 10;
    for(int i = 1;i <= n;i++) {
        a[i].x = rd(), a[i].y = rd(), a[i].z = rd();
    }
    sort(a+1,a+1+n);
    for(int i = 1;i <= n;i++) {
        x = a[i].x, y = a[i].y, z = a[i].z;
//        cout << x << " " << y << " " << z << endl;
        tot += y;
//        tothigh += y;
        for(int j = 0;j <= tot;j++) {
            dp[i][j+y][1] = max(dp[i-1][j+x-last][1],dp[i-1][j+x-last][0]);
            dp[i][j][0] = max(dp[i-1][j+x-last][1],dp[i-1][j+x-last][0]);
            if(dp[i][j][0] != -INF-1) dp[i][j][0] += z;
        }
        last = x;
        for(int j = 0;j <= tot;j++) {
            if(dp[i][j][0] >= h) {
                printf("%d
",x);
                return 0;
            }
        }
    }
    int life = 10;
    for(int i = 1;i <= n;i++) {
        if(a[i].x <= life) life += a[i].y;
    }
    printf("%d
",life);
    return 0;
}