题解 P1156 【垃圾陷阱】
ljc20020730
2019-07-06 20:50:34
在本题中，我们按照时间这一维度进行动态规划。
设$ f_{i,j}$ 表示时间轴前 $i$ 个单位时间，奶牛生命值为 $j$ 时，奶牛的最大高度。
注意到，同一个时间轴节点上可能会同时扔下多个垃圾，所以在每个时间点中需要使用$01$背包模型来挑选垃圾的不同决策。
首先，这个时间轴节点可能没有扔下垃圾或者即使扔下垃圾也不使用，这样的话转移就是 $ f_{i,j}=f_{i-1,j+1}$。
其次，对于某一个垃圾有两种使用方法，叠起来($f_{i,j}+h$)或者用来恢复生命($f_{i,j-f}$)
所以，在01背包中转移可以这么写$f_{i,j} = max\{f_{i,j}+h,f_{i,j-f}\}$
注意倒序取即可。
为了处理方便对于不可能的决策，我们直接把其值赋为负无穷。
如果在动态规划过程中$ f_{i,j}≥D $ 那么在 $ i $ 时刻奶牛已经爬出井。
如果在动态规划过程中$ f_{i,j}≥ 0 $那么在 $i$ 时刻奶牛仍然存活。
最后输出即可。
```cpp
# include <bits/stdc++.h>
using namespace std;
const int N=4e3+10,M=4e3+10;
struct rec{
int f,h;
}a[N];
int f[N][M],D,G;
vector<int>w[N];
int main()
{
scanf("%d%d",&D,&G);
int MaxT=4000,SumF=4000;
for (int i=1;i<=G;i++) {
int t; scanf("%d",&t);
scanf("%d%d",&a[i].f,&a[i].h);
w[t].push_back(i);
}
memset(f,-0x3f,sizeof(f));
f[0][10]=0; bool ok=false; int alive=0,ans=0x3f3f3f3f;
for (int i=1;i<=MaxT;i++) {
for(int j=0;j<=SumF;j++) f[i][j]=f[i-1][j+1];
for (int k=0;k<w[i].size();k++)
for (int j=SumF;j>=0;j--) {
f[i][j]=f[i][j]+a[w[i][k]].h;
if (j-a[w[i][k]].f>=0) f[i][j]=max(f[i][j],f[i][j-a[w[i][k]].f]);
}
for(int j=0;j<=SumF;j++){
if (f[i][j]>=D) ok=true,ans=min(ans,i);
if (f[i][j]>=0) alive=max(alive,i);
}
}
if (ok==false) printf("%d\n",alive);
else printf("%d\n",ans);
return 0;
}
```