势利的小卖部 （HGOI 2019.2.15 T1）

 题目大意：题目已经最简洁了，除了第一句话的背景以外都是简洁的。。 数据范围：钱数小于等于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; } ```