洛谷$P1156$ 垃圾陷阱 $dp$
正解:$dp$
解题报告:
传送门!
然后这题,首先看到要么吃要么堆起来就会想到$01$背包趴?然后就考虑设方程
考虑设$f_{i,j}$表示投入第$i$个物品能活到第$j$天的最大高度.
转移就$f_{i,j}=max\{f_{i-1,j}+H_i,f_{i-1,j-F_i}\}$
然后如果$f_{i,j}\geq D$就说明能逃出来
否则找到$f_{i,j}$有值的$j_{max}$(其实可以直接能吃就吃直到活不下去位置$QwQ$
注意前一个式子有$f_{i-1,j}\not=-1$的约束,后一个式子有$j-F_i\geq t_i$的约束.
$over$
#include<bits/stdc++.h>
using namespace std;
#define my(i,x,y) for(int i=x;i>=y;--i)
#define rp(i,x,y) for(int i=x;i<=y;++i)
const int N=100+10,T=5000+10;
int d,g,f[N][T];
struct node{int t,f,h;}nod[N];
bool cmp(node gd,node gs){return gd.t<gs.t;}
int main()
{
scanf("%d%d",&d,&g);rp(i,1,g)scanf("%d%d%d",&nod[i].t,&nod[i].f,&nod[i].h);sort(nod+1,nod+1+g,cmp);
memset(f,-1,sizeof(f));f[0][10]=0;//rp(i,0,10)f[0][i]=0;
rp(i,1,g)rp(j,nod[i].t,T-10){if(~f[i-1][j])f[i][j]=f[i-1][j]+nod[i].h;if(j-nod[i].f>=nod[i].t)f[i][j]=max(f[i][j],f[i-1][max(0,j-nod[i].f)]);if(f[i][j]>=d)return printf("%d\n",nod[i].t),0;}
int nw=10;rp(i,1,g){if(nw<nod[i].t)return printf("%d\n",nw),0;nw+=nod[i].f;}printf("%d\n",nw);
return 0;
}