POJ3616-Milking Time-(dp)

题意：牛有m个时间段可以挤奶，每个时间段的开始时间，结束时间，挤奶量不尽相同，寄完一次需要休息r时间，求在n时间内如何安排牛挤奶产量最大。

解题：

1.休息r时间，当做结束时间需要+r

2.以结束时间的先后对各个时间段排序，然后dp求最值。dp[i]表示当前到了第i个时间段。

3.状态转移方程：dp[i] = max( dp[i],dp[j]+a[i].v );

4.条件：当前i时间段的挤奶任务的开始时间 >= 以前j时间段的结束时间

简而言之，对m个时间段遍历，每次都求当前时间段及以前的时间段一起挤奶量最大化。当前的dp[i]产量与以前时间段的最大挤奶量续上本次时间段的产量。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<math.h>

#include<string>

#include<map>

#include<queue>

#include<stack>

#include<set>

#define ll long long

#define inf 0x3f3f3f3f

#define p 1000000007

using namespace std;

int n,m,r;

struct node

{

    int l;

    int r;

    int v;

};

node a[];

int dp[];

bool cmp( node p1,node p2 )

{

    return p1.r<p2.r;

}

int main()

{

    while( scanf("%d %d %d",&n,&m,&r)!=EOF )

    {

        memset(dp,,sizeof(dp));

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

            scanf("%d %d %d",&a[i].l,&a[i].r,&a[i].v),a[i].r+=r;

        sort(a+,a+m+,cmp);

        /*

        printf("\n");

        for(int i=1;i<=m;i++)

        printf("%d %d %d \n",a[i].l,a[i].r,a[i].v);

        */

        int maxx=-inf;

        for(int i=;i<=m;i++)///当前的时间段

        {

            dp[i]=a[i].v;///先赋值 第i个时间段自己的产量

            //printf("dp[%d]=%d\n",i,dp[i]);观察dp变化

            for(int j=i-;j>=;j--)///接前面的时间段

            {

                if( a[i].l >= a[j].r )

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

            }

            //printf("dp[%d]=%d\n",i,dp[i]);

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

        }

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

    }

    return ;

}

巴特西

POJ3616-Milking Time-(dp)

最新文章

热门文章