POJ 3616

==>原题链接

题目概述

总时间为n，有m个时间段，每个段有一个权值w，让你选一些不冲突的时间段给奶牛挤奶，得到最高的总权值。注意每次挤牛奶要有一个休息时间r，需要做一下小处理。

思路

DP。区间DP。DP的特点是 对状态的记录 和 传递。
变换了DP类型还是有点不适应，其实思路异乎寻常的简单。

dp[i] = max(dp[i], dp[j] + num[i].w);

dp[i]表示选取前i段，其中包含第i段的最大权值。那么就是枚举i段之前的那些空余时间可满足的段。

以前i我们已经很熟悉了，是利用传递阶段信息的办法得出前一个阶段的最优结果。必须包含i段使得整个式子能枚举到每一种情况但不重样，是出于有序性的一种合理的强制规定，你可以规定别的，但是这样规矩减少维度，同时很方便，应该熟练。

代码

#include <stdio.h>
#include <algorithm>

using namespace std;

typedef struct
{
    int st, en, w;
} DATA;

DATA num[1000+10];
int dp[1000000+10];

bool cmp(DATA a, DATA b);

int main()
{
    int i, j;
    int n, m, r, ans = 0;

    freopen("3616.in", "r", stdin);
    scanf("%d%d%d", &n, &m, &r);
    n += r;

    for (i = 0; i < m; i++)
    {
        scanf("%d%d%d", &num[i].st, &num[i].en, &num[i].w);
        num[i].en += r;
    }

    sort(num, num + m, cmp);

    for (i = 0; i < m; i++)
    {
        dp[i] = num[i].w;
    }

    for (i = 0; i < m; i++)
    {
        for (j = 0; j < i; j++)
        {
            if(num[i].st >= num[j].en)
            {
                dp[i] = max(dp[i], dp[j] + num[i].w);
            }
        }

        ans = max(ans, dp[i]);
    }

    printf("%d\n", ans);


    return 0;
}

bool cmp(DATA a, DATA b)
{
    if (a.st == b.st)
    {
        return a.en < b.en;
    }
    else
    {
        return a.st < b.st;
    }
}