题解 | 毕业bg

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct student;
int n;
vector<student>bg;
struct student {
    int h;
    int l;
    int t;
    student(int h, int l, int t) :h(h), l(l), t(t) {
    }
    //按结束时间从小到大排序
    bool operator<(const student& s)const {
        return t < s.t;
    }
};
int res = 0;
void dfs(int i, int sum, int now) {
    //分别代表当前是第几个party，快乐度总和是多少，如今的时间
    if (i == n) {
        //说明此时已经枚举完所有party了
        res = max(res, sum);
        return;
    }
    //不选这场party参见
    dfs(i + 1, sum, now);
    //这里进行了剪枝
    if (now + bg[i].l <= bg[i].t) {
        //只有参加完节目之前，创办人不离开才会选这个party参加
        dfs(i + 1, sum + bg[i].h, now + bg[i].l);
    }
}
int main()
{
    int h, l, t;
    int a, b;
    int i;

    while (scanf("%d", &n) != EOF && n >= 0)
    {
        res = 0;
        bg.clear();
        for (int i = 0; i < n; i++) {
            cin >> h >> l >> t;
            bg.push_back(student(h, l, t));
        }
        sort(bg.begin(), bg.end());
        //开始dfs
        dfs(0, 0, 0);
        cout << res<<endl;
    }

}
// 64 位输出请用 printf("%lld")