背包问题][P1156 垃圾陷阱]做题思路和总结"/>
[动态规划][背包问题][P1156 垃圾陷阱]做题思路和总结
题目描述
卡门――农夫约翰极其珍视的一条Holsteins
奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方,它的深度为D(2≤D≤100)英尺。
卡门想把垃圾堆起来,等到堆得与井同样高时,她就能逃出井外了。另外,卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放,并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间t(0<t≤1000),以及每个垃圾堆放的高度h(1≤h≤25)和吃进该垃圾能维持生命的时间f(1≤f≤30),要求出卡门最早能逃出井外的时间,假设卡门当前体内有足够持续10小时的能量,如果卡门10小时内没有进食,卡门就将饿死。
思路
其实不难发现,通过阅读题面可以发现背包问题的气息(垃圾可以通过排序,将高度作为背包容量,补充的能量为价值),用DP[i][j]表示考虑前i个垃圾,垃圾高度为j的时候,奶牛可以得到的最大能量,如果在某一次DP运算的时候最大能量不小于0(等于0的时候,奶牛可以在濒死状态下进行操作)的时候,j>=D的时候就可以逃出陷阱。如果找不到,接下来遍历寻找最大存活时间。
显然DP[0][0] = 10.这是最初的状态;
DP数组最初应该初始化为-INF,0为濒死状态,应该考虑进运算。
进行状态转移运算的时候要考虑奶牛能量的损耗(这就是存在代码(Rubbish[i].T-Rubbish[i-1].T)的原因)
当找不到逃出方案的时候,寻找最长存活时间,应该从DP数组遍历(某一种状态的能量最大值加上垃圾出现的时间),不断获取最大值。
代码
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;struct _Rubbish
{int T;int H;int F;
}Rubbish[1001];int D,G;
int INF = 0XFFFFF;
int DP[101][1001] = {0};bool cmp(_Rubbish,_Rubbish);int main(void)
{cin >> D >> G;for(int i = 1;i <= G;i++){cin >> Rubbish[i].T >> Rubbish[i].F >> Rubbish[i].H;}sort(Rubbish+1,Rubbish+G+1,cmp);for(int i = 0;i <= G;i++){for(int j = 0;j <= D;j++){DP[i][j] = -INF;}}DP[0][0] = 10;Rubbish[0].T = Rubbish[0].F = Rubbish[0].H = 0;for(int i = 1;i <= G;i++){for(int j = 0;j <= D;j++){//Eat or non-Eat//濒死状态(Life == 0)的时候也可以吃if(DP[i-1][j]-(Rubbish[i].T-Rubbish[i-1].T) >= 0){DP[i][j] = max(DP[i][j],DP[i-1][j]+Rubbish[i].F-(Rubbish[i].T-Rubbish[i-1].T));}if(j-Rubbish[i].H >= 0 && DP[i-1][j-Rubbish[i].H]-(Rubbish[i].T-Rubbish[i-1].T) >= 0){DP[i][j] = max(DP[i][j],DP[i-1][j-Rubbish[i].H]-(Rubbish[i].T-Rubbish[i-1].T));if(j >= D){cout << Rubbish[i].T << endl;return 0;}}}}int ans = 0;for(int i = 0;i <= G;i++){for(int j = 0;j <= D;j++){if(DP[i][j] != - INF){ans = max(ans,DP[i][j]+Rubbish[i].T);}}}cout << ans << endl;return 0;
}bool cmp(_Rubbish a,_Rubbish b)
{return a.T < b.T;
}
更多推荐
[动态规划][背包问题][P1156 垃圾陷阱]做题思路和总结
发布评论