Milking Time POJ - 3616
  anLrwkgbyYZS 2023年12月30日 9 0


题意: 总共 N 小时 , M 个产奶时段, 每次产奶后需要休息  R 小时。

    给你 M 组数据, 每组数据 包括 :时段的开始时间点, 结束时间点, 时间段产奶量。

思路: 将所有时间段 按 结束时间点 从小到大 排序。

              dp[i] 是以 第 i 个时间段结束时的最大产奶量 (排序后),有点像最大序列和,不过需要考虑两个时间的休息时段,即 j 时间段 发生后 i 时间段 能否发生。

for(i=1; i<=m; i++) // 不断 更新 dp[i] 的最优值 
 {
 dp[i] = c[i].v; 

  for(j=1; j<i; j++) // 和前面的比较(更新后) 更新dp[i]  
  {
    if((c[j].e+r) <= c[i].s) // 如果 j  时间段 发生后 i 时间段 能发生, 则更新 dp[i]
    dp[i] = max(dp[i],dp[j]+c[i].v);       
  }
  
   if(dp[i] > ans)
     ans = dp[i]; // 记录最大值结果 
    }
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef struct worktime
{
    int s, e, v;
} WT;
WT c[2010];
int dp[1010];
int main()
{
    int i, j, n, m, r;
    scanf("%d %d %d",&n,&m,&r);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d",&c[i].s,&c[i].e,&c[i].v);
    }

    for(i=1; i<m; i++)
        for(j=i+1; j<=m; j++)
        {
            if(c[i].e > c[j].e)
            {
                WT temp;
                temp = c[i];
                c[i] = c[j];
                c[j] = temp;
            }
        }

    memset(dp,0,sizeof(dp));

    int ans = -1;

    for(i=1; i<=m; i++) // 不断 更新 dp[i] 的最优值
    {
        dp[i] = c[i].v;

        for(j=1; j<i; j++) // 和前面的比较(更新后) 更新dp[i]
        {
            if((c[j].e+r) <= c[i].s)
                dp[i] = max(dp[i],dp[j]+c[i].v);
        }

        if(dp[i] > ans)
            ans = dp[i]; // 记录最大值结果
    }

    printf("%d",ans);
    return 0;
}

 

 

 

 

 

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年12月30日 0

暂无评论

anLrwkgbyYZS