dp[i] 表示到达time_i时获得的最大价值，dp[i] = max(dp[i - 1],dp[end_timej - start_timej] + valuej),因为还有个休息时间，每次挤奶会多占用rest_time,如果end_timej + rest_time > n，令其取n则可，这样原本的end_timej ~ n 这一段也不会用于挤其他奶牛。
#include<iostream> #include<vector> #define debug(x) cout<<#x<<" is "<<x<<endl #define pb push_back #define se second #define fi first #define mp make_pair using namespace std; const int N = 1e6 + 5; typedef long long ll; ll dp[N],n,m,rest; vector<pair<int,int> > interval[N]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>rest; for(int i = 1;i <= m;i++){ int l,r,value; cin>>l>>r>>value; r = min(r + rest, n); if(r >= 1 && r <= n) interval[r].pb(mp(l,value)); } for(int i = 1;i <= n;i++){ dp[i] = dp[i - 1]; for(int j = 0;j < interval[i].size();j++){ int left = interval[i][j].fi,val = interval[i][j].se; dp[i] = max(dp[i],dp[left] + val); } } cout<<dp[n]<<endl; return 0; }