dp+贪心——2019 NCPC A

把结论推出来就完事了

#include <bits/stdc++.h>
#define maxn 100000005
using namespace std;
int dp[maxn];
struct Node{
    int l,w,h;
    bool operator <(const Node &b)const{
        return w>b.w;
    }
}q[100005];
int main()
{
    int n,d;
    scanf("%d%d",&n,&d);
    for(int i=0;i<n;i++) scanf("%d%d%d",&q[i].l,&q[i].w,&q[i].h);
    sort(q,q+n);
    int res=0;
    for(int i=0;i<n;i++){
        if(dp[q[i].w]+q[i].l>d) res++;
        for(int j=q[i].w;j<min(2*q[i].w,(int)1e8+2);j++){
            dp[j-q[i].w]=max(dp[j-q[i].w],dp[j]+q[i].h);
        }
    }
    printf("%d
",res);
}