题目链接 http://poj.org/problem?id=3616

题意：在一个农场里，在长度为N个时间可以挤奶，但只能挤M次，且每挤一次就要休息t分钟；

接下来给m组数据表示挤奶的时间与奶量求最大挤奶量

看似很复杂其实就是求大递增序列即可，先将M次挤奶进行排序按照end从小到大排序然后判断s[i].sta-r>=s[j].end时可以加上。

#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;struct TnT {    int sta , ed , va;}s[1024];long long dp[1024];bool cmp(TnT a , TnT b) {    return a.ed < b.ed;}int main() {    int n , m , r;    scanf("%d%d%d" , &n , &m , &r);    memset(s , 0 , sizeof(s));    for(int i = 1 ; i <= m ; i++) {        scanf("%d%d%d" , &s[i].sta , &s[i].ed , &s[i].va);    }    sort(s + 1 , s + m + 1 , cmp);    long long MAX = 0;    for(int i = 1 ; i <= m ; i++) {        dp[i] = s[i].va;    }    for(int i = 1 ; i <= m ; i++) {        for(int j = 1 ; j < i ; j++) {            if(s[i].sta - r >= s[j].ed) {                dp[i] = max(dp[i] , dp[j] + s[i].va);            }            MAX = max(MAX , dp[i]);        }    }    printf("%lld\n" , MAX);    return 0;}

poj 3616 Milking Time (基础dp)