POJ--3616 Milking Time(DP)

记录
19:52 2024-1-26

http://poj.org/problem?id=3616

reference:《挑战程序设计竞赛(第2版)》第二章练习题索引 p135

一个LIS(最长上升子序列, Longest Increasing Subsequence)问题的变种
dp[i]表示第i个interval结尾能获得最多的milk，首先需要把数据按照起始时间排序，第i个表示以这个工作结尾可以获得的最大的milk，那么公式就为
dp[i]=max(dp[i],dp[j]+a[i].c)（a[j].e+r<=a[i].s,j<i)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX_N 1000
#define MAX_M 1000
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;

int N, M, R;
typedef struct {
    int begin, end;
    int value;
} t;
t datas[MAX_N];

bool cmp(const t& lhs, const t& rhs) {
    return lhs.begin < rhs.begin || (lhs.begin == rhs.begin && lhs.end < rhs.end);
}
int dp[MAX_M]; //LIS(Longest Increasing Subsequence)变式 dp1[i]表示第i个interval结尾能获得最多的milk
// dp[i]=max(dp[i],dp[j]+a[i].c)（a[j].e+r<=a[i].s,j<i)

void solve() {
    sort(datas + 1, datas + M + 1, cmp);
    for(int i = 1; i <=M; i++) {
        dp[i] = datas[i].value;
        for(int j = 1; j < i; j++) {
            if(datas[j].end + R < datas[i].begin) {
                dp[i] = max(dp[i], dp[j] + datas[i].value);
            }
        }
    }
    int result = -1;
    for(int i = 1; i <= M; i++) {
        if(result <= dp[i]) {
            result = dp[i];
        }
    }
    printf("%d\n", result);
}

int main() {
    scanf("%d%d%d", &N, &M, &R);
    t temp;
    for(int i = 1; i <= M; i++) {
        scanf("%d%d%d", &(temp.begin), &(temp.end), &(temp.value));
        // printf("%d %d %d\n", temp.begin, temp.end, temp.value);
        datas[i] = temp;
    }
    solve();    
}