题目链接:

题意:

奶牛Bessie在0~N时间段产奶。农夫约翰有M个时间段可以挤奶，时间段f,t内Bessie能挤到的牛奶量e。奶牛产奶后需要休息R小时才能继续下一次产奶，求Bessie最大的挤奶量。

题解:

定义dp[i]表示第i个时间段挤奶能够得到的最大值，拆开来说，就是前面 i – 1个时间段任取0到i – 1个时间段挤奶，然后加上这个时间段（i）的产奶量之和。dp[i]满足如下递推关系：

第i个时间段挤奶的最大值 = 前 i – 1 个时间段挤奶最大值中的最大值 + 第i次产奶量。

代码:

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 typedef long long ll; 6 #define MS(a) memset(a,0,sizeof(a)) 7 #define MP make_pair 8 #define PB push_back 9 const int INF = 0x3f3f3f3f;10 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;11 inline ll read(){12     ll x=0,f=1;char ch=getchar();13     while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}14     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}15     return x*f;16 }17 //18 const int maxn = 1e3+10;19 20 struct node{21     int l,r,e;22     bool operator<(const node& rhs)const{23         return l < rhs.l;24     }25 }cow[maxn];26 27 int dp[maxn];28 29 int main(){30     int N,M,R;31     cin >> N >> M >> R;32     for(int i=0; i
         
          > cow[i].l >> cow[i].r >> cow[i].e;34         cow[i].r += R;35     }36     sort(cow,cow+M);37 38     // dp[i] : 表示第i个时间段挤奶能够得到的最大值，拆开来说，就是前面 i – 1个时间段任取0到i – 1个时间段挤奶，然后加上这个时间段（i）的产奶量之和39 40     for(int i=0; i