贪心+背包
这道题比较坑的就是我们的对于相同截止时间的需要排个序，因为我们这个工作是有时间前后顺序的，我们如果不排序的话我们一些截止时间晚的工作就无法得到最优报酬
#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;
}
原文地址：https://blog.csdn.net/wniuniu_/article/details/140679459
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！