题意：奶牛Bessie在0~N时间段产奶。农夫约翰有M个时间段可以挤奶，时间段f,t内Bessie能挤到的牛奶量e。奶牛产奶后需要休息R小时才能继续下一次产奶，求Bessie最大的挤奶量。
详见代码
1 #include <stdio.h> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <memory> 7 #include <iostream> 8 #define LL long long 9 using namespace std; 10 struct Node { 11 int s,e,v; 12 friend bool operator < (Node a,Node b) { 13 return a.s<b.s; 14 } 15 }; 16 Node node[1010]; 17 int main() { 18 int n,m,r; 19 while(~scanf("%d%d%d",&n,&m,&r)) { 20 for(int i=0; i<m; i++) { 21 scanf("%d%d%d",&node[i].s,&node[i].e,&node[i].v); 22 node[i].e+=r;//每次增加休息时间 23 } 24 sort(node,node+m);//时间小的优先级高 25 int dp[1010];//i表示在i时间点前符合题意的最大值 26 memset(dp,0,sizeof(dp)); 27 for(int i=0; i<m; i++) { 28 dp[i]=node[i].v; 29 for(int j=0; j<i; j++) { 30 if(node[j].e<=node[i].s) {//判断条件 31 dp[i]=max(dp[i],dp[j]+node[i].v); 32 } 33 } 34 } 35 cout<<*max_element(dp,dp+m)<<endl; 36 } 37 return 0; 38 }