Milking Time

直接翻译了

Descriptions

贝茜是一个勤劳的牛。事实上，她如此专注于最大化她的生产力，于是她决定安排下一个N（1≤N≤1,000,000）小时（方便地标记为0..N-1），以便她生产尽可能多的牛奶。

农民约翰有一个M（1≤M≤1,000）可能重叠的间隔列表，他可以在那里进行挤奶。每个区间我有一个起始小时（0≤starting_houri≤N），一个结束小时（starting_houri <ending_houri≤N），以及相应的效率（1≤efficiencyi≤1,000,000），表示他可以从中获取多少加仑的牛奶。贝西在那段时间。 Farmer John分别在开始时间和结束时间开始时开始和停止挤奶。在挤奶时，Bessie必须在整个间隔内挤奶。

尽管贝茜有其局限性。在任何间隔期间挤奶后，她必须休息R（1≤R≤N）小时才能再次开始挤奶。鉴于Farmer Johns的间隔清单，确定Bessie在N小时内可以产生的最大牛奶量。

Input

*第1行：三个以空格分隔的整数：N，M和R
*第2行.M +1：第i + 1行描述FJ的第i个挤奶间隔，其中包含三个以空格分隔的整数：开始时间_i，结束时间 _i和效率_i

Output

*第1行：Bessie在N小时内可以产生的最大加仑牛奶数

Sample Input

Sample Output

题目链接

https://vjudge.net/problem/POJ-3616

对于每一次挤奶,结束时间+=休息时间.

先把M次挤奶按照开始时间排个序,用dp[i]表示挤完第i个时间段的最大挤奶量,那么有:

 for(int i=; i<M; i++)

    {

        dp[i]=a[i].f;

        for(int j=; j<i; j++)

            if(a[j].e<=a[i].s)//结束时间小于下一次的开始时间

                dp[i]=max(dp[i],dp[j]+a[i].f);

    }

答案不是dp[M]而是max(dp[i]) (1<=i<=M) (因为不一定最后一次挤奶是最大的一次).

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 1005

using namespace std;

int N,M,R;

int dp[Maxn];

struct node

{

    int s,e,f;//开始时间 结束时间 效率

    bool operator<(const node &c) const//按开始时间排序

    {

        return s<c.s;

    }

};

node a[Maxn];

int main()

{

    cin>>N>>M>>R;

    for(int i=; i<M; i++)

    {

        cin>>a[i].s>>a[i].e>>a[i].f;

        a[i].e+=R;//结束时间=结束时间+休息时间

    }

    sort(a,a+M);//排序

    for(int i=; i<M; i++)

    {

        dp[i]=a[i].f;

        for(int j=; j<i; j++)

            if(a[j].e<=a[i].s)//结束时间小于下一次的开始时间

                dp[i]=max(dp[i],dp[j]+a[i].f);

    }

    int ans=dp[];

    for(int i=;i<M;i++)

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

    cout<<ans<<endl;

    return ;

}

巴特西

【POJ - 3616】Milking Time（动态规划）

Milking Time

最新文章

热门文章