Milking Time poj-3616_C

题目链接：3616 -- Milking Time

题面：

题意：有一只奶牛，有m次工作的机会，给定开始时间和结束时间和工资，每次工作完了以后会休息r小时，问最多可以拿到多少工资

思路：动态规划，如果我们选择在某个时间段工作，那么我们就可以从结束时间开始到n都获得工资，由此可以得到状态转移方程：

dp[j] = max(dp[j], dp[max(0, arr[i].l - r)] + arr[i].val);

但是这样子总时间为n，那么时间复杂度就是O（n*m），会tle，我们可以通过离散化的方式，将总时间差不多将到2*m,时间复杂度为O(m*m)即可

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define pi pair
#define ll long long
#define endl "\n"
vector ve;
struct node{
    int val;
    int l, r;
}arr[1005];
bool cmp(node a, node b){
    if(a.r != b.r){
        return a.r < b.r;
    }
    return a.l < b.l;
}
int dp[1000005];
int findx(int x){
    return lower_bound(ve.begin(), ve.end(), x) - ve.begin();
}
int main(){
    int n, m, r;
    while(cin >> n >> m >> r){
        ve.clear();
        for(int i = 0; i < m; i++){
            cin >> arr[i].l >> arr[i].r >> arr[i].val;
            ve.push_back(max(0, arr[i].l - r));
            ve.push_back(arr[i].r);
        }
        sort(ve.begin(), ve.end());
        ve.erase(unique(ve.begin(), ve.end()), ve.end());
        sort(arr, arr + m, cmp);
        for(int i = 0; i <= ve.size(); i++){
            dp[i] = 0;
        }
        for(int i = 0; i < m; i++){
            for(int j = ve.size(); j >= findx(arr[i].r); j--){
                dp[j] = max(dp[j], dp[findx(max(0, arr[i].l - r))] + arr[i].val);
            }
        }
        cout << dp[ve.size()] << endl;
    }
    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/562299.html

Milking Time poj-3616

发表评论

评论列表（0条）