题解 P1156 【垃圾陷阱】

· · 题解

很显然的想到f[i][j]。

但是！翻了翻题解，发现第一页竟然没有第二维表示血量的题解，这让花了一小时处理细节的蒟蒻非常不开森！！！

so，我来发一篇，交代一下细节，传授一下大道。（炫耀一下一小时的努力成果

主要就是for循环中的两个if。

请看注释：

#include<bits/stdc++.h>
using namespace std;
int n,d;
int dp[201][20201];
struct node {
    int t,f,h;
}q[201];
bool cmp(node a,node b) {
    return a.t<b.t;
}
int main() {
    cin>>d>>n;
    for(int i=1;i<=n;i++) cin>>q[i].t>>q[i].f>>q[i].h;
    sort(q+1,q+n+1,cmp);
    if(q[1].t>10) {     //很显然的特判，其实不加也可以。 
        cout<<"10";
        return 0;
    }
    for(int i=0;i<=n;i++) for(int j=20200;j>=0;j--) dp[i][j]=-99999999;   //其实j的范围没必要开这么大，但大一点比较稳。 
    dp[0][10]=0;                   //初始化 
    for(int i=1;i<=n;i++) {   
        for(int j=0;j<=3200;j++) {      //此处j的循环要注意，范围是3200以上大概都可以
                                            //但这个for循环还与上面的预处理有关联
                                            //因为下面有调用 j+(q[i].t-q[i-1].t) ，所以 预处理时j的范围应该比此处循环的范围大1000 左右 

            if(j+(q[i].t-q[i-1].t)>=0&&dp[i-1][j+(q[i].t-q[i-1].t)]+q[i].h>=0) dp[i][j]=max(dp[i][j],dp[i-1][j+(q[i].t-q[i-1].t)]+q[i].h);
            if(j+(q[i].t-q[i-1].t)-q[i].f>=q[i].t-q[i-1].t&&dp[i-1][j+(q[i].t-q[i-1].t)-q[i].f]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j+(q[i].t-q[i-1].t)-q[i].f]);
            //往上第一个if判断，f[i][j]由f[i-1][j+(q[i].t-q[i-1].t)-q[i].f]转移而来，转移时必须满足的一个条件时，转移前的血量足够支撑到转移。
            //也就是 j+(q[i].t-q[i-1].t)-q[i].f (转移前) >= q[i].t-q[i-1].t
            if(dp[i][j]==d&&j!=1) {
                cout<<q[i].t<<endl;
                return 0;
            }

        }
    }
    int tail=10;
    for(int i=1;i<=n;i++) {
        if(q[i].t<=tail) tail+=q[i].f;
    }
    cout<<tail;
}

手动模拟查错一小时，我太难了