首页 > 试题广场 >

考试策略

[编程题]考试策略

小明同学在参加一场考试，考试时间 2 个小时。试卷上一共有 n 道题目，小明要在规定时间内，完成一定数量的题目。考试中不限制试题作答顺序，对于 i 第道题目，小明有三种不同的策略可以选择:

(1)直接跳过这道题目，不花费时间，本题得0分。

(2)只做一部分题目，花费 pi 分钟的时间，本题可以得到 ai 分。

(3)做完整个题目，花费 qi 分钟的时间，本题可以得到 bi 分。

小明想知道，他最多能得到多少分。

数据范围： $1 \le n \le 100 \$ ， $1 \le p_i,q_i \le 120 \$ ， $0 \le a_i \le b_i \le 1000 \$

第一行输入一个n数表示题目的数量。

接下来n行，每行四个数p_i，a_i，q_i，b_i。

输出一个数，小明的最高得分。

示例1

输入

4
20 20 100 60
50 30 80 55
100 60 110 88
5 3 10 6

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师动态规划美团 2019 Java工程师

来自：美团2019年秋招部分...

上传者：小小

难度：

0条回答 79收藏 9554浏览

查看代码

扫一扫，把题目装进口袋