长乐 DAY10

今天是dp专题，难度不用说，贴段代码过了

#include
using namespace std;
int tt,n,k,res;
long long dp[100000],ans;
struct node
{
    int a,p,t;
}f[100000];
bool cmp(node x,node y)
{
    return x.a<y.a;
}
int main()
{
    freopen("frenzy.in","r",stdin);
    freopen("frenzy.out","w",stdout);
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d",&n,&k);
        res=0;
        for(int i=1;i<=n;i++) scanf("%d%d%d",&f[i].a,&f[i].p,&f[i].t),res=max(res,f[i].p);
        dp[0]=0;
        for(int i=1;i<=k+res;i++) dp[i]=10000000000000;
        sort(f+1,f+n+1,cmp);
        for(int i=1;i<=n;i++)
            for(int j=f[i].a+f[i].p;j<=k+res;j++)
                dp[j]=min(dp[j],dp[j-f[i].p]+f[i].t);
        ans=10000000000000;
        for(int i=k;i<=k+res;i++) ans=min(ans,dp[i]);
        printf("%lld\n",ans);
    }
    return 0;
}