HDU-1881 毕业bg (01背包变形)

毕业bg

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5303 Accepted Submission(s): 1971

Problem Description 每年毕业的季节都会有大量毕业生发起狂欢,好朋友们相约吃散伙饭,网络上称为“bg”。参加不同团体的bg会有不同的感觉,我们可以用一个非负整数为每个bg定义一个“快乐度”。现给定一个bg列表,上面列出每个bg的快乐度、持续长度、bg发起人的离校时间,请你安排一系列bg的时间使得自己可以获得最大的快乐度。

例如有4场bg: 第1场快乐度为5,持续1小时,发起人必须在1小时后离开; 第2场快乐度为10,持续2小时,发起人必须在3小时后离开; 第3场快乐度为6,持续1小时,发起人必须在2小时后离开; 第4场快乐度为3,持续1小时,发起人必须在1小时后离开。 则获得最大快乐度的安排应该是:先开始第3场,获得快乐度6,在第1小时结束,发起人也来得及离开;再开始第2场,获得快乐度10,在第3小时结束,发起人正好来得及离开。此时已经无法再安排其他的bg,因为发起人都已经离开了学校。因此获得的最大快乐度为16。

注意bg必须在发起人离开前结束,你不可以中途离开一场bg,也不可以中途加入一场bg。 又因为你的人缘太好,可能有多达30个团体bg你,所以你需要写个程序来解决这个时间安排的问题。

Input 测试输入包含若干测试用例。每个测试用例的第1行包含一个整数N (<=30),随后有N行,每行给出一场bg的信息: h l t 其中 h 是快乐度,l是持续时间(小时),t是发起人离校时间。数据保证l不大于t,因为若发起人必须在t小时后离开,bg必须在主人离开前结束。

当N为负数时输入结束。

Output 每个测试用例的输出占一行,输出最大快乐度。

Sample Input 3 6 3 3 3 2 2 4 1 3 4 5 1 1 10 2 3 6 1 2 3 1 1 -1

Sample Output 7 16

01背包问题 思路: 首先将各个活动排序,按照发起人离校时间进行升序排序 为什么要进行排序呢?因为背包问题的解法有一个特点,它是逆向解决问题的,也就是说,状态转移方程执行完之后,实际上是物品按照逆序放进去,先放最后一个。因为这道题目每个聚会都有一个属性,就是发起人离校时间,如果不排序,最后一个活动的发起人离校时间不是最大的,那么就得不到最优解。

#include <iostream>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include<algorithm>  


using namespace std;

int n;
int dp[1000][1000];
struct Node
{
    int h;
    int l;
    int t;
}Arry[35];
int cmp(Node x,Node y)
{
    return x.t<y.t;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n<0)
            break;
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&Arry[i].h,&Arry[i].l,&Arry[i].t);
        sort(Arry+1,Arry+n+1,cmp);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=Arry[n].t;j++)
            {
                if(j<=Arry[i].t&&j-Arry[i].l>=0)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-Arry[i].l]+Arry[i].h);
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        int ans=0;
        for(int i=1;i<=Arry[n].t;i++)
        {
            if(ans<dp[n][i])
                ans=dp[n][i];
        }
        printf("%d\n",ans);


    }
    return 0;

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏牛客网

京东【Java实习】海外党远程二面

惯例先放一面面经链接:https://www.nowcoder.com/discuss/74319 直入正题: 1. JVM内存模型说一下? 2. GC回收的...

39770
来自专栏CSDN技术头条

黑客与C语言

“黑客”这个词想必我们已经如雷贯耳了。我们一听到黑客通常在大脑中的印象就是一群穿着黑衣,躲在小屋里偷偷用着数台电脑针对某组计算机,神不知鬼不觉地进行攻击。他们通...

1.2K80
来自专栏ACM算法日常

为什么vjudge上他人公开的代码要以图片形式显示?

vjudge用图片来显示代码,应该是为了避免抄袭。在较低水平的oier中,已经有交别人的代码来通过题目的风气。举个例子,洛谷上抄袭代码情况极其严重,而u...

13220
来自专栏牛客网

阿里2018暑期实习内推面经(Java岗),offer已拿到

整个三月份通过牛客网和网友分享的经验学到了很多东西,现在反馈一下我的面试经历,希望对同学们有帮助。 个人情况:大三本EE方向渣硕,经过实验室学长内推,于三月底完...

86850
来自专栏java一日一条

Java常见异常及解释

常见 Java 异常解释:(译者注:非技术角度分析。阅读有风险,理解需谨慎:))

18620
来自专栏域名资讯

域名资讯:近期交易的数字域名与拼音域名价格

数字域名流通性较强,而且建站上没有太大局限性,因此很是受投资人和终端喜爱。而拼音域名很符合中国互联网市场的需求,也是很多米农和企业喜欢的类型。近日...

27570
来自专栏非典型技术宅

iOS传感器:利用磁力计完成一个AR场景应用1. 磁力计的介绍2. 磁力计的使用3. 开始我们的小案例

21840
来自专栏Python中文社区

微信小程序头脑王者辅助神器

起步 最近直播答题火热,群里也经常看到比拼微信小程序《头脑王者》。我比较笨,凭纯答题只到了黑金段位。鉴于本周刚刚点亮了收集抓包的技能,于是想试着通过这个来做一个...

59880
来自专栏工科狗和生物喵

【我的漫漫跨考路】数据结构之堆栈的线性实现

正文之前 ? 昨天晚上阶段性的完成了一部分数学的复习(一元积分学终于搞定了,后面的貌似没这么难了),所以今天打算撸一撸代码,结合前几天写的链表实现线性存储,今天...

29760
来自专栏牛客网

51一面面经

13900

扫码关注云+社区

领取腾讯云代金券