【动态规划】POJ3616-Milking Time

【题目大意】

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

【思路】

首先按各个时间段的开始时间进行排序。f[i]表示到第i个时间段位置挤奶量的最大值。

对于当前时间段，如果它之前的时间段的结束时间+休息时间≤当前时间段的开始时间(cow[j].e+r<=cow[i].s)，那么进行比较(f[i]=max(f[i],f[j]+cow[i].v))。

【易错点】

注意f[i]的初值是cow[i].v，即只有当前时间段挤奶。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int MAXN=+;

 struct node

 {

     int s,e,v;

     bool operator < (const node &x) const

     {

         return s<x.s;

     }

 }cow[MAXN];

 int f[MAXN];

 int n,m,r;

 int main()

 {

     scanf("%d%d%d",&n,&m,&r);

     for (int i=;i<m;i++)

     {

         scanf("%d%d%d",&cow[i].s,&cow[i].e,&cow[i].v);

     }

     sort(cow,cow+m);

     for (int i=;i<m;i++) f[i]=cow[i].v;

     for (int i=;i<m;i++)

         for (int j=;j<i;j++)

         {

             if (cow[j].e+r<=cow[i].s)

                 f[i]=max(f[i],f[j]+cow[i].v);

         }

     int ans=-;

     for (int i=;i<m;i++) ans=max(ans,f[i]);

     cout<<ans<<endl;

     return ;

 }