题解 P1156 【垃圾陷阱】

· · 题解

终于搞懂这个题怎么写了

  1. 首先这个题目有好想却不那么好写O(GD \Sigma f)的写法，按照洛谷以前的速度是可以AC的，现在在别的oj也可以卡着将近1000ms通过，但是洛谷过不了了233

思路很简单：考虑“看题说话”，把题目里面的相关量都加入状态。

状态转移方程：其中f(i,j,k)表示状态为第i个辣鸡，当前处在高度j，剩余的生命长度为k。\Delta T代表这个垃圾和下个垃圾之间的时间差。

f(i,j,k)= \begin{cases} t_i & \text{ 如果 } j+h_i \geq d \\ \min \begin {cases} f(i+1,j,k+f_i- \Delta T) & \text { 如果 } k+f_i \geq \Delta T \\ f(i+1,j+h_i,k-\Delta T) & \text { 如果 } k \geq \Delta T \\ \infty & \text { 若不满足上述 } \end{cases} & \text{ 如果 } j+h_i < d \end{cases}

这样求出的就是最短的爬上去的时间，然后如果不可能爬上去的话就只吃垃圾不放垃圾就行了

  1. 然后就是O(GD)的解法了，我对着网上各种刷表法的题解懵逼了很久，所以这里给出一种基于填表的解法

考虑第i个辣鸡，我们有两种选择，吃掉和堆起来。令g(i,j)代表处理到了第i个物品，在高度j的最大死亡时刻。

于是显然可以从g(i-1,j-h_i)与g(i-1,j)转移而来。

方程如下：

g(i,j)= \begin{cases} g(i-1,j-h_i)& \text{ 如果 } j \geq h_i \text{且} g(i-1,j-h_i) \geq t_i \\ g(i-1,j)+f_i& \text{ 如果 } g(i-1,j) \geq t_i \\ g(i-1,j)& \text{ 若不满足上述 } \end{cases}

实际上可以采用滚动数组省去g(i,j)的第一维

最后上代码：

Solution 1:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Item{
    int t,f,h;
    bool operator<(const Item& it){
        return t<it.t;
    }
};
const int MAXG=100,MAXD=100,INF=1e9;
int D,G,opt[MAXG+1][MAXD+1][3011];
Item P[MAXG+10];
int main(){
    scanf("%d%d",&D,&G);
    for(int i=1;i<=G;i++)
        scanf("%d%d%d",&P[i].t,&P[i].f,&P[i].h);
    sort(P+1,P+G+1);
    P[G+1].t=(INF<<1);
    for(int i=G;i>=1;i--)
        for(int j=D-1;j>=0;j--)
            for(int k=0;k<=3010;k++) {
                int Tm=P[i+1].t-P[i].t;
                if(j+P[i].h>=D) opt[i][j][k]=P[i].t;
                else{
                    opt[i][j][k]=(INF<<1);
                    if(k+P[i].f>=Tm) 
                        opt[i][j][k]=min(opt[i][j][k],opt[i+1][j][k+P[i].f-Tm]);
                    if(k>=Tm)
                        opt[i][j][k]=min(opt[i][j][k],opt[i+1][j+P[i].h][k-Tm]);
                }
            }
    if(P[1].t>10) printf("10\n");
    else {
        if(opt[1][0][10-P[1].t]<INF-10) printf("%d\n",opt[1][0][10-P[1].t]);
        else {
            int k=10-P[1].t;
            for(int i=1;i<=G;i++) {
                static int Tm;
                Tm=P[i+1].t-P[i].t;
                if(k+P[i].f<Tm) {
                    printf("%d\n",P[i].t+k+P[i].f);
                    return 0;
                } else
                    k=k+P[i].f-Tm;
            }
        }
    }
    return 0;
}

Solution 2:

#include <cstdio>
#include <algorithm>
using namespace std;
struct Garbage{ int t,f,h; };
const int MAXD=100, MAXG=100, MAXH=25;
const int INF=0x3f3f3f3f;
int D,G,p1,p2,tot,opt[(MAXD+MAXG*MAXH)<<1];
Garbage P[MAXG+10];
bool cmp(const Garbage& x,const Garbage& y) { return x.t<y.t; }
int main(){
    scanf("%d%d", &D, &G);
    tot=D;
    for(int i=1;i<=G;i++){
        scanf("%d%d%d", &P[i].t, &P[i].f, &P[i].h);
        tot+=P[i].h;
    }
    sort(P+1,P+G+1,cmp);
    opt[0]=10;
    for(int i=1;i<=G;i++)
        for(int j=tot;j>=0;j--) {
            p1=p2=0;
            if(j>=P[i].h && opt[j-P[i].h]>=P[i].t) p1=opt[j-P[i].h];
            if(opt[j]>=P[i].t) p2=opt[j]+P[i].f;
            if(p1!=0 || p2!=0)
                opt[j]=max(p1,p2);//上述条件都不满足时，p1=p2=0，应该让opt[j]保持原样 
                                  //为何不设置为0呢？考虑一下opt[0]就知道了。假设只有一个物品在11s时掉落。
            if(j>=D && opt[j]!=0) {
                printf("%d\n",P[i].t);
                return 0;
            }
        }
    printf("%d\n",opt[0]);
}