题意：牛有m个时间段可以挤奶，每个时间段的开始时间，结束时间，挤奶量不尽相同，寄完一次需要休息r时间，求在n时间内如何安排牛挤奶产量最大。
解题：
1.休息r时间，当做结束时间需要+r
2.以结束时间的先后对各个时间段排序，然后dp求最值。dp[i]表示当前到了第i个时间段。
3.状态转移方程：dp[i] = max( dp[i],dp[j]+a[i].v );
4.条件：当前i时间段的挤奶任务的开始时间 >= 以前j时间段的结束时间
简而言之，对m个时间段遍历，每次都求当前时间段 及以前的时间段 一起 挤奶量最大化。当前的dp[i]产量 与 以前时间段的最大挤奶量续上本次时间段的产量。
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #define ll long long #define inf 0x3f3f3f3f #define p 1000000007 using namespace std; int n,m,r; struct node { int l; int r; int v; }; node a[10086]; int dp[10086]; bool cmp( node p1,node p2 ) { return p1.r<p2.r; } int main() { while( scanf("%d %d %d",&n,&m,&r)!=EOF ) { memset(dp,0,sizeof(dp)); for(int i=1;i<=m;i++) scanf("%d %d %d",&a[i].l,&a[i].r,&a[i].v),a[i].r+=r; sort(a+1,a+m+1,cmp); /* printf(" "); for(int i=1;i<=m;i++) printf("%d %d %d ",a[i].l,a[i].r,a[i].v); */ int maxx=-inf; for(int i=1;i<=m;i++)///当前的时间段 { dp[i]=a[i].v;///先赋值 第i个时间段自己的产量 //printf("dp[%d]=%d ",i,dp[i]);观察dp变化 for(int j=i-1;j>=1;j--)///接前面的时间段 { if( a[i].l >= a[j].r ) dp[i] = max( dp[i],dp[j]+a[i].v ); } //printf("dp[%d]=%d ",i,dp[i]); maxx=max(maxx,dp[i]); } printf("%d ",maxx); } return 0; }