阅读量:0
这道题比较坑的就是我们的对于相同截止时间的需要排个序，因为我们这个工作是有时间前后顺序的，我们如果不排序的话我们一些截止时间晚的工作就无法得到最优报酬
#include<bits/stdc++.h> using namespace std; #define int long long int t; int n; const int N = 5005; struct node{ int t,end,pr; int start; bool operator<(node b){ if(end<b.end) return 1; return 0; } }e[N]; int ans = 0; int dp[N]; signed main(){ cin >> t; while(t--){ cin >> n; int tmax = 0; for(int i=1;i<=n;i++){ cin >> e[i].t >> e[i].end >> e[i].pr; e[i].start = e[i].end - e[i].t; tmax = max(tmax,e[i].end); } sort(e+1,e+1+n); for(int i=0;i<=5004;i++) dp[i] = 0; for(int i=1;i<=n;i++){ for(int j=e[i].end;j>=e[i].t;j--){ dp[j] = max(dp[j],dp[j-e[i].t]+e[i].pr); } } int ans = 0; for(int i=1;i<=tmax;i++) ans = max(ans,dp[i]); cout << ans << endl; } return 0; } 