题目链接：https://www.luogu.org/problemnew/show/P1156
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #include <sstream> #include <iostream> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> using namespace std; #define ll long long #define re register #define fi first #define se second #define mp make_pair #define pb push_back #define P pair<int,int> void read(int &a) { a=0; int d=1; char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch-'0'; while(ch=getchar(),ch>='0'&&ch<='9') a=a*10+ch-'0'; a*=d; } void write(int x) { if(x<0) putchar(45),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } struct note { int t,u,w; }q[105]; int f[105];///f[i] i为当前高度，f[i]表示当前生命 bool cmp(note x,note y) { return x.t<y.t; } int main() { int d,g; read(d); read(g); for(re int i=1;i<=g;i++) { read(q[i].t); read(q[i].u); read(q[i].w); } sort(q+1,q+1+g,cmp);///因为题目没说垃圾按顺序给，所以要排序。。。 int now=0; f[0]=10; for(re int i=1;i<=g;i++)///枚举，跟01背包一样 for(re int j=d;j>=0;j--) { if(f[j]-q[i].t>=0)///这里不知道为什么可以等于0，卡样例卡半年。 { if(j+q[i].w>=d)///在满足自己不饿死的情况下，只要当前高度+给的垃圾的高度>d很明显就能输出了 return write(q[i].t),0; f[j+q[i].w]=max(f[j+q[i].w],f[j]);///新给的垃圾高度加上，更新生命值 f[j]+=q[i].u;///吃下这个垃圾，为下次计算做准备。 } } write(f[0]); return 0; }