Problem 3615 --竞赛总分(inflate)

3615: 竞赛总分(inflate)

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $6$ 正确数量 $5$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划
    学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能多得分。
    现在要进行一次竞赛,总时间T固定,有若干类型可选择的题目,每种类型题目可选入的数量不限,每种类型题目有一个si(解答此题所得的分数)和ti(解答此题所需的时间),现要选择若干题目,使解这些题的总时间在T以内的前提下,所得的总分最大。
    输入包括竞赛的时间M(1 <= M <= 10000)和题目类型数目N(1 <= N <= 10000)。
    后面的每一行将包括两个整数来描述一种"题型":
    第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。
第 1 行:
两个整数:竞赛的时间M和题目类型数目N。
第 2-N+1 行:
两个整数:每种类型题目的分数和耗时。
单独的一行,在给定固定时间里得到的最大的分数。
300 4
100 60
250 120
120 100
35 20
605

推荐代码 查看3615 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$4 $ms] 只能过个样例~~~ 729276 2021-04-03 21:56:40
内存最少[$2020 $KB] 月落星辰挽 829677 2022-03-27 21:31:15
第一AC 只能过个样例~~~ 729276 2021-04-03 21:56:40
第一挑战 只能过个样例~~~ 729276 2021-04-03 21:56:40

赛题来源/所属竞赛 J:第十章《动态规划》 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1638 2021信息学/ACM集训(二)-动态规划 2021-04-04 09:00:00 请登录