AC率因为这一道题……
在定义域内单调递减……做*落体运动……沉淀不反……
所以我来说说这道题。
其实是一个有些小变化的背包问题。对于一个新的物品 i ,有选个不选两种情况。那么定义 f [ i ] [ j ] 为第 i 件物品,高度为 j 时的体力值,而这个值我定义的是不随着消耗减小,而是直接和落下的那件物品的时间比较即可。
那么对于两种情况:
1.选:
f [ i ] [ j + h ] = max ( f [ i ] [ j + h ] , f [ i - 1 ] [ j ] ) ;
2.不选:
f [ i ] [ j ] = f [ i - 1 ] [ j ] + w ;
但是显然第一维是没有意义的(甚至我都不知道上面的方程对不对) ,完全可以压成一维。
那么就是:
f [ j + h ] = max ( f [ j + h , f [ j ] ) ;
f [ j ] + = w ;
这样就可以,如果发现在有生命的情况下,高度大于等于所需高度,那么就可以直接输出了,否则,最后输出高度为0(一直吃)的生命。
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; #define maxn 5000 int f[maxn]; struct node { int t,w,h; } a[maxn]; bool cmp(node x,node y) { return x.t<y.t; } int d,g,ans=10,cnt; int main() { scanf("%d%d",&d,&g); for(int i=1; i<=g; i++) scanf("%d%d%d",&a[i].t,&a[i].w,&a[i].h); sort(a+1,a+1+g,cmp); f[0]=10; for(int i=1; i<=g; i++) { for(int j=d; j>=0; j--) { if(f[j]<a[i].t) continue; if(j+a[i].h>=d) { printf("%d",a[i].t); return 0; } f[j+a[i].h]=max(f[j+a[i].h],f[j]); f[j]+=a[i].w; } } printf("%d",f[0]); return 0; }