[題解]luogu P1156 垃圾陷阱

前言：[數據刪除]

來源：題解

---

不發題面了

重要内容：分析 i,j 代表什么：

按時間順序排序然後依次轉移，時間數值不固定或者比較大不太好做階段，而且會有很多浪費，所以用前 i 個物品轉移，轉移時在判可行性，處理掉了時間，

只剩 血量，高度兩維，在考慮怎麼分配，如果用血量做第二維的話數值仍然不確定而且可能很大，於是嘗試交換，對於能否活下來在最後找解的時候在判斷。

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int d,g;

struct node{

    int t,h,f;

}e[];

int f[][];//i個物品j高度的最大血量（重要

bool cmp(node a,node b)

{

    return a.t<b.t;

}

int main()

{

    scanf("%d%d",&d,&g);

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

        scanf("%d%d%d",&e[i].t,&e[i].f,&e[i].h);

    }

    sort(e+,e++g,cmp);

    f[][]=;//初值

    for(int i=;i<=g;i++)

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

        if(f[i-][j]>=e[i].t)//如果上一個狀態的血量夠用

        f[i][j]=max(f[i][j],f[i-][j]+e[i].f);//吃

        if(j>=e[i].h&&f[i-][j-e[i].h]>=e[i].t)//如果可以從前一個更低的高度加上這個物品的高度，並且能堅持到下一個垃圾

        f[i][j]=max(f[i][j],f[i-][j-e[i].h]);//填

    }

    int maxh=,maxt=,i;

    for(i=;i<=g;i++){

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

            if(f[i][j]-e[i].t>=)//一定要判狀態能否使用

            maxh=max(maxh,j);//更新最高高度

            maxt=max(maxt,f[i][j]);//每次都要更新最長時間

        }

        if(maxh>=d)break;

    }

    if(maxh>=d)printf("%d",e[i].t);

    else printf("%d",maxt);

}