[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 =  + ;

const int MAXM =  + ;

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][];

inline int rd() {

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)) {f=ch=='-'?-:;ch=getchar();}

    while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

    return x*f;

}

int main() {

    scanf("%d%d",&h,&n);

    int x,y,z;

    last = ;

    memset(dp,~0x3f,sizeof(dp));

    dp[][][] = ;

    tot = ;

    for(int i = ;i <= n;i++) {

        a[i].x = rd(), a[i].y = rd(), a[i].z = rd();

    }

    sort(a+,a++n);

    for(int i = ;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 = ;j <= tot;j++) {

            dp[i][j+y][] = max(dp[i-][j+x-last][],dp[i-][j+x-last][]);

            dp[i][j][] = max(dp[i-][j+x-last][],dp[i-][j+x-last][]);

            if(dp[i][j][] != -INF-) dp[i][j][] += z;

        }

        last = x;

        for(int j = ;j <= tot;j++) {

            if(dp[i][j][] >= h) {

                printf("%d\n",x);

                return ;

            }

        }

    }

    int life = ;

    for(int i = ;i <= n;i++) {

        if(a[i].x <= life) life += a[i].y;

    }

    printf("%d\n",life);

    return ;

}