卡门――农夫约翰极其珍视的一条
Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为 D(2≤D≤100)英尺。卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间 t(0<t≤1000)，以及每个垃圾堆放的高度 h(1≤h≤25)和吃进该垃圾能维持生命的时间 f(1≤f≤30)，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续 10小时的能量，如果卡门 10小时内没有进食，卡门就将饿死。
是一道经典的dp题,并没有太大的难度,但有值得注意的地方
题目中存在三个元素:时间,高度,生命
其中生命和时间都处于时间轴中,显然依照时间轴划分阶段,根据直觉应当以垃圾掉落时间划阶段
接着生命和高度都可以作为状态.
如果以生命作为状态
- 数据范围大,导致复杂度(常数)大
- 处于时间轴中,设计转移策略时可能干扰思路
- 转移策略较复杂,且不方便枚举
总之显得很不自然
所以应当选定高度作为状态
接着设计转移策略时:
- 填表法:注意到如果高度大于D(即卡门已经得救时),难以枚举
- 刷表法:自然且方便判定死亡或得救
总体上是一道考验代码能力的题目.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define llint long long
using namespace std;
int xx[2][200],*dp[2];
struct xxx{
int t,f,h;
bool operator < (const xxx &be)const{
if (t != be.t)
return t < be.t;
if (f != be.t)
return f > be.f;
return h > be.f;
}
}tra[200];
int main (){
int D,G,ans = 0x3f3f3f3f,ans2 = 0;
cin >> D >> G;
for (int i = 1;i <= G;++ i)
scanf("%d%d%d",&tra[i].t,&tra[i].f,&tra[i].h);
sort(tra + 1,tra + 1 + G);
memset(xx,-1,sizeof(xx));
dp[0] = xx[0];dp[1] = xx[1];
dp[1][0] = 10;
for (int i = 1;i <= G;++ i){
swap(dp[0],dp[1]);
for (int j = 0;j < D;++ j){
if (dp[0][j] < tra[i].t)
continue;
if (j + tra[i].h >= D) ans = min(ans,tra[i].t);
dp[1][j + tra[i].h] = max(dp[1][j + tra[i].h],dp[0][j]);
dp[1][j] = max(dp[1][j],dp[0][j] + tra[i].f);
ans2 = max(ans2,dp[1][j]);
}
}
if (ans == 0x3f3f3f3f){
cout << ans2;
return 0;
}
cout << ans;
return 0;
}以上.