首页 > 试题广场 >

倒卖战利品

[编程题]倒卖战利品
  • 热度指数：3923 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在游戏中，击败魔物后，薯队长获得了N件宝物，接下来得把这些宝物卖给宝物回收员来赚点小钱。这个回收员有个坏毛病，每次卖给他一件宝 物后，之后他就看不上比这件宝物差的宝物了。在这个世界中，衡量宝物的好坏有两个维度，稀有度X和实用度H，回收员在回收一个宝物A 后，下一个宝物的稀有度和实用度都不能低于宝物A。那么薯队长如何制定售卖顺序，才能卖给回收员宝物总个数最多。 

输入描述:
第一行一个正整数N。 接下来N行。每行两个整数分别表示X    和    H X1    H1 X2    H2 … XN    HN
输入限制： 对于70%的数据： 
0<N<10^4 
0<Xi<10^6 
0<Hi<10^6 
100%的数据：
0<N<10^6
0<Xi<10^6 
0<Hi<10^6


输出描述:
一个整数，表示最多可以卖出的宝物数
示例1

输入

4
3 2
1 1 
1 3
1 2

输出

3
算法知识视频讲解
开通博客
头像 ActivePony
发表于 2020-06-15 20:34:06
> 首先要注意，题目中的条件有误，应该是严格大于而不是大于等于。 排序+动态规划（暴力搜索） 首先按照第一个维度将数组从小到大排序，第一个维度相同的，按照第二个维度从小到达排序。这样以来，问题就被转换为最大上升子序列问题。使用动态规划求解即可。状态定义为：以第i个元素结尾的上升子序列的最大长度 展开全文
去ta的博客 赞 (1) 回复(2) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 前端工程师 算法工程师 测试开发工程师 小红书 2020 Java工程师
上传者：小小
难度：
21条回答 7629浏览

热门推荐

通过挑战的用户

相关试题

倒卖战利品

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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