首页 > 试题广场 >

毕业bg

[编程题]毕业bg
  • 热度指数：2860 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
    每年毕业的季节都会有大量毕业生发起狂欢，好朋友们相约吃散伙饭，网络上称为“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你，所以你需要写个程序来解决这个时间安排的问题。

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

    当N为负数时输入结束。


输出描述:
    每个测试用例的输出占一行，输出最大快乐度。
示例1

输入

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

输出

7
16
算法知识视频讲解
开通博客
头像 limitcc
发表于 2022-03-01 20:49:05
总体采用动态规划思想，不过在规划之前，需要按离开时间对每一个bg进行排序，将离开时间早的排在前面。 然后再离开时间到开始时间内进行循环动态规划即可。 #include <iostream> #include <cstring> #include <algorithm&g 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 牛客805753209号
发表于 2025-03-02 11:12:41
#include <stdio.h> #include <stdlib.h> void Swap(int *a,int *b){ int tmp=*a; *a=*b; *b=tmp; } void Sort(int bg[][3],int n){ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 AARun
发表于 2023-03-30 00:55:32
#include <iostream> #include<vector> #include<algorithm> #include<string> #include<cstdio> using namespace std; struct 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 古瑶
发表于 2025-03-18 22:09:42
解法一：背包问题变形 #include <iostream> #include <vector> #include <algorithm> using namespace std; //经典背包问题加了个时间限制 struct BG { int h; // 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 爱吃的懒羊羊离上岸不远了
发表于 2025-03-15 20:59:52
#include <iostream> #include <algorithm> #include <cstring> #include <cmath> #define maxn 35 using namespace std; typedef str 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 程昱同学
发表于 2023-01-27 13:13:17
#include <iostream> #include <vector> #include<algorithm> using namespace std; int N; struct BG { int h; int l; int t; } 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客142529159号
发表于 2023-03-17 19:58:49
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 31; struct DB { int w, v, t; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客596495425号
发表于 2025-03-18 11:33:24
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include<vector> #include<algorithm> using namespace std; struct student; int n; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 宁静的冬日
发表于 2022-03-14 19:48:00
dfs永远滴神 #include<iostream> #include<vector> #include<algorithm> using namespace std; #define MAX 1000 int N, M; struct act{ int l;/ 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 搜索 dfs
难度：
17条回答 6650浏览

热门推荐

通过挑战的用户

查看代码

相关试题

毕业bg

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号