题意：一共有n个任务，然后给你每个任务的开始时间 和结束时间以及这个任务能达到的价值。然后每次做完一个任务后要休息r个时间，问你最大可以得到的价值和 这个比贪心中的节目问题多了一个权值。然后用动态规划，其中的时间要排序,按照开始的时间从小到大排序，那样的话，我们后面就比较好操作了。 dp[i]:表示在做第i个任务得到的最大价值和 然后两重循环 状态转移：dp[i]=max(dp[i],dp[j]+a[i].ef);表示，如果第i个任务被选了的最大价值 然后我们不知道最后第i个任务有没有被选，也就是说dp[i]就是第i个任务一定被选。所以最后还要取dp中的一个最大值，不一定是dp[m]！
//刚开始想的是用dp[i]:第i时间的最大价值，然后超时了。
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; const int maxn = 1000005; int dp[1005]; struct node { int bg,ed,ef; }; node a[1005]; bool cmp(node a1,node a2) { if(a1.bg!=a2.bg) return a1.bg<a2.bg; else return a1.ed<a2.ed; } int main() { int n,m,r; scanf("%d %d %d",&n,&m,&r); for(int i=1;i<=m;i++){ scanf("%d %d %d",&a[i].bg,&a[i].ed,&a[i].ef); a[i].ed+=r; } sort(a+1,a+m+1,cmp); for(int i=1;i<=m;i++) { dp[i]=a[i].ef; for(int j=i-1;j>=1;j--) { if(a[i].bg>=a[j].ed){ dp[i]=max(dp[i],dp[j]+a[i].ef); } } } int ans=0; for(int i=1;i<=m;i++) ans=max(ans,dp[i]); printf("%d\n",ans); return 0; }