Problem 2903 --3.1.2 Score Inflation

2903: 3.1.2 Score Inflation

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $34$ 正确数量 $18$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 usaco 动态规划 背包

The more points students score in our contests, the happier we here at the USACO are. We try to design our contests so that people can score as many points as possible, and would like your assistance.

We have several categories from which problems can be chosen, where a "category" is an unlimited set of contest problems which all require the same amount of time to solve and deserve the same number of points for a correct solution. Your task is write a program which tells the USACO staff how many problems from each category to include in a contest so as to maximize the total number of points in the chosen problems while keeping the total solution time within the length of the contest.

The input includes the length of the contest, M (1 <= M <= 10,000) (don't worry, you won't have to compete in the longer contests until training camp) and N, the number of problem categories, where 1 <= N <= 10,000.

Each of the subsequent N lines contains two integers describing a category: the first integer tells the number of points a problem from that category is worth (1 <= points <= 10000); the second tells the number of minutes a problem from that category takes to solve (1 <= minutes <= 10000).

Your program should determine the number of problems we should take from each category to make the highest-scoring contest solvable within the length of the contest. Remember, the number from any category can be any nonnegative integer (0, one, or many). Calculate the maximum number of possible points.


Line 1:  M, N -- contest minutes and number of problem classes 
Lines 2-N+1:  Two integers: the points and minutes for each class
A single line with the maximum number of points possible given the constraints.

300 4
100 60
250 120
120 100
35 20
605

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

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$35 $ms] zlzhu 470036 2019-09-19 11:08:13
内存最少[$0 $KB] syly 531777 2019-11-23 16:18:04
第一AC 计爱玲 448861 2019-07-24 15:05:10
第一挑战 计爱玲 448856 2019-07-24 14:33:39

赛题来源/所属竞赛 usaco training usaco Training

竞赛编号 竞赛名称 竞赛时间 访问比赛
1407 2019CCPC模拟赛(秦皇岛站 安财贸9.19) 2019-09-19 09:00:00 请登录