[LuoguP1156] 垃圾陷阱

一道很恶心的背包 DP

需要考虑很玄学的的细节

总之,要精心判断是否能转移,再转移

结合刷表法和填表法

详细的看 Luogu 题解去吧

#include<bits/stdc++.h>
using namespace std;
const int G=102;
int d,g,ans;

struct data{int t,f,h;};
data t[G];
bool cmp(data x,data y){return x.t<y.t;}

int f[G][G];
//f[i,j] 前 i 个垃圾,在第 i 个垃圾尚未处理时高度为 j 时的最大生命值

int main(){scanf("%d%d",&d,&g);
    for(int i=1;i<=g;i++)scanf("%d%d%d",&t[i].t,&t[i].f,&t[i].h);
    sort(t+1,t+g+1,cmp);
    memset(f,0xc0,sizeof(f));
    f[0][0]=10;
    for(int i=1;i<=g;i++){for(int j=0;j<=d;j++){if(f[i-1][j]>=t[i].t){f[i][j]=max(f[i][j],f[i-1][j]+t[i].f);// 吃
                f[i][j+t[i].h]=max(f[i][j+t[i].h],f[i-1][j]);// 放
                if(j+t[i].h>=d){printf("%d",t[i].t);
                    return 0;
                }
            }
            ans=max(ans,f[i][j]);
        }
    }
    printf("%d",ans);
    return 0;
}

 上一篇
IOI1999 花店橱窗布置 IOI1999 花店橱窗布置
分析动态规划法,用 表示用了 朵花,摆了 个花瓶的最大美学值 (不一定要摆第 个花瓶), 表示第 i 朵花摆第 个花瓶中最大的一个花瓶的美学值 f[i,j]=\ma
2018.10.01
下一篇 
C++ 那些事 C++ 那些事
文常本文介绍一些有关 c++ 的文常 数据类型大小 类型 含义 字节数 /byte void 无 0 bool 布尔类型 1 (unsigned) char 字符型 1 (unsigned) short 短整型 2
2018.10.01
  目录