题解 | #毕业bg#动态规划加滚动数组

#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstdio>
using namespace std;

struct node{
    int h,l,t;
};//分别保存快乐度，持续时间，离校时间

bool cmp(node n1,node n2){
    return n1.t<n2.t;
}

int main() {
    int n;
    int h,l,t;
    int maxt;//保存最大的离校时间
    while (scanf("%d",&n)!=EOF&&n>0) {
        maxt=0;
        vector<node>bg(n);
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&h,&l,&t);
            bg[i].h=h;//快乐度
            bg[i].l=l;//持续时间
            bg[i].t=t;//离校时间
            if(t>maxt)//找到最大的离校时间
            	maxt=t;
        } 

        vector<int>dp(maxt+1,0);//将最大离校时间作为背包大小，加1是习惯
        sort(bg.begin(),bg.end(),cmp);
        int maxhappy=0;//保存最大的快乐值
        for(int i=0;i<bg.size();i++){
            for(int j=bg[i].t;j>=bg[i].l;j--){
//如果是二维数组的话，i代表第几件物品，dp[i][j]的值应该是在不取当前物品跟取当前物品两种情况中取最大值，
//即dp[i-1][j],dp[i-1][j-bg[i].l]+bg[i].h中取最大值
//因此，在滚动数组中如果从前往后遍历，前面的j在将本次i代表的物品放入背包后，
//后面的j如果将dp[i-1][j-bg[i].l]+bg[i].h设为自身dp值的话，就会导致本次遍历放入bg[i]这一物品多次
//因此使用一维滚动数组的话应该从后往前遍历
                dp[j]=max(dp[j],dp[j-bg[i].l]+bg[i].h);
                if(dp[j]>maxhappy)
                    maxhappy=dp[j];
            }
        }
        printf("%d\n",maxhappy);
    }
    return 0;
}
// 64 位输出请用 printf("%lld")