Luogu1156垃圾陷阱|题解

Luogu1156垃圾陷阱|题解

七月 20, 2018

卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方,它的深度为 D(2≤D≤100)D(2 \le D \le 100)D(2≤D≤100) 英尺。

卡门想把垃圾堆起来,等到堆得与井同样高时,她就能逃出井外了。另外,卡门可以通过吃一些垃圾来维持自己的生命。

每个垃圾都可以用来吃或堆放,并且堆放垃圾不用花费卡门的时间。

假设卡门预先知道了每个垃圾扔下的时间 t(0<t≤1000)t(0< t \le 1000)t(0<t≤1000) ,以及每个垃圾堆放的高度 h(1≤h≤25h(1 \le h \le 25h(1≤h≤25 )和吃进该垃圾能维持生命的时间 f(1≤f≤30)f(1 \le f \le 30)f(1≤f≤30) ,要求出卡门最早能逃出井外的时间,假设卡门当前体内有足够持续 101010 小时的能量,如果卡门 101010 小时内没有进食,卡门就将饿死。

是一道经典的dp题,并没有太大的难度,但有值得注意的地方

题目中存在三个元素:时间,高度,生命

其中生命和时间都处于时间轴中,显然依照时间轴划分阶段,根据直觉应当以垃圾掉落时间划阶段

接着生命和高度都可以作为状态.

如果以生命作为状态

  1. 数据范围大,导致复杂度(常数)大
  2. 处于时间轴中,设计转移策略时可能干扰思路
  3. 转移策略较复杂,且不方便枚举

总之显得很不自然

所以应当选定高度作为状态

接着设计转移策略时:

  1. 填表法:注意到如果高度大于D(即卡门已经得救时),难以枚举
  2. 刷表法:自然且方便判定死亡或得救

总体上是一道考验代码能力的题目.

#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;
}

以上.