势利的小卖部 (HGOI 2019.2.15 T1)

2019-02-15 13:49:17


题目大意:题目已经最简洁了,除了第一句话的背景以外都是简洁的。。

数据范围:钱数小于等于5000,商品数小于等于500

那么,显然这是一道背包

但更显然的是不能直接背包

那么,我们要排个序

排序规律是按照$a_1-b_1<a_2-b_2$的顺序排。为什么呢?因为如果1排在2之前,那么显然要保证$a_1+b_2<a_2+b_1$,这样可以保证尽可能地把两个都买进。

剩下就很简单了,普通背包一下就好了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
struct ASD
{
    int a,b,v;
}p[510];
int f[5100];
bool cmp(ASD x,ASD y)
{
    if(x.a-x.b==y.a-y.b) return x.b>y.b;
    return x.a-x.b<y.a-y.b;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].v);
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++)
        for(int j=p[i].b;j<=m;j++)
            f[j-p[i].a]=max(f[j-p[i].a],f[j]+p[i].v);
    int ans=0;
    for(int i=0;i<=m;i++)
        ans=max(f[i],ans);
    printf("%d",ans);
    return 0;
}