[HOJ] 43 - 太空電梯

#include<stdio.h>
#include<algorithm>
using namespace std;
struct P{
    int x,y,z;
}s[400];
int cmp(P a,P b){
    return a.y<b.y;
}
int dp[40005]={0};
int main(){
    int t,n,i,j,k,ans=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].z);
    sort(s,s+n,cmp);
    for(i=0;i<n;i++)
        for(j=0;j<s[i].z;j++)
            for(k=s[i].y;k>=s[i].x;k--)
                dp[k]=max(dp[k],dp[k-s[i].x]+s[i].x),ans=max(ans,dp[k]);
    printf("%d\n",ans);
}