P1156 垃圾陷阱

  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;
}

 

  

上一篇:P1156 垃圾陷阱


下一篇:P1156 垃圾陷阱