题解 | #毕业bg#

总体采用动态规划思想，不过在规划之前，需要按离开时间对每一个bg进行排序，将离开时间早的排在前面。

然后再离开时间到开始时间内进行循环动态规划即可。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct bg{
    int happy;
    int time;
    int leavetime;
    bool operator<(bg next){
        return leavetime < next.leavetime;
    }
};

const int MAXN = 30;
bg arr[MAXN];
int dp[1000];

int main(){
    int n;
    while(cin >> n){
        if(n<0) break;
        int leavetime;
        for(int i=0;i<n;i++)
            cin >> arr[i].happy >> arr[i].time >> arr[i].leavetime;
        memset(dp,0,sizeof(dp));
        sort(arr,arr+n);
        int maxAns = 0;
        
        for(int i=0;i<n;i++){
            for(int currenttime = arr[i].leavetime;currenttime>=arr[i].time;currenttime--){
                dp[currenttime] = max(dp[currenttime-arr[i].time]+arr[i].happy,dp[currenttime]);
                maxAns = max(maxAns,dp[currenttime]);
            }
        }
        cout << maxAns << endl;
        }
    
    return 0;
}