POJ 3616 Milking Time(类最长递增子序列)

Description

奶牛有N个小时的产奶时间，农夫有M个时间段可用于挤牛奶，奶牛在相应的时间段有不同的产奶量，每挤一次牛奶必须休息R分钟，求最多能挤奶多少？

Analyze

将每一段的右界加上R作为新的右界。如果前一段区间的右界 <= 后一段区间的左界，那么两段可以同时取得。但由于每段的权值未知，可能存在与之冲突的一个时间段的权值较之更大，所以要择优。

对每个时间段dp，dp[i]表示选择了第i个时间段，整个过程可以达到的最大挤奶量

初始化dp[i] = a[i].val

对之前的区间遍历(前提：排好序)，若a[j].r <= a[i].l

那么当前区间最优值可从dp[j] + a[i].val和dp[i]中取max，这里像是最长递增子序列的dp过程：

1. 对某组有序的元素dp
2. 初始化dp[i] = a[i]
3. 遍历 i 之前的元素 j ，若 a[j] <= a[i] 表示 i 前面可连上 j (此时 i 地状态可更新为更优值dp[i] = max(dp[i], dp[j] + a[i]))

此类算法可解决的问题？

1. 有序的多个元素(可以是数字、区间)
2. 某些元素之间满足某种关系就具有某种“可连接性”，且“连接”可能引起最优值的更新

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

struct node
{
    int l, r, val;
} a[1005];

bool cmp(node a, node b)
{
    return a.l < b.l;
}

int dp[1005];

int main()
{
    int n, m, len;
    scanf("%d%d%d", &n, &m, &len);
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].val);
        a[i].r += len;
    }
    sort(a, a + m, cmp);
    for(int i = 0; i < m; ++i)
    {
        dp[i] = a[i].val;
        for(int j = 0; j < i; ++j)
            if(a[j].r <= a[i].l)
                dp[i] = max(dp[i], dp[j] + a[i].val);
    }
    int ans = -0x3f3f3f3f;
    for(int i = 0; i < m; ++i)
        ans = max(ans, dp[i]);
    cout << ans << '\n';
    return 0;
}
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40