【dp】饥饿的牛
2024-08-30 07:19:44
普通dp题
题目描述
牛在饲料槽前排好了队。饲料槽依次用1到n（1 ≤ n ≤ 2000）编号。每天晚上，一头幸运的牛根据约翰的规则，吃其中一些槽里的饲料。 约翰提供b个区间的清单。一个区间是一对整数start-end，1 ≤ start ≤ end ≤ n，表示一些连续的饲料槽，比如1-3,7-8,3-4等等。牛可以任意选择区间，但是牛选择的区间不能重叠。 当然，牛希望自己能够吃得越多越好。给出一些区间，帮助这头牛找一些区间，使它能吃到最多的东西。 在上面的例子中，1-3和3-4是重叠的，不能同时选择；聪明的牛选择1-3和7-8，这样可以吃到5个槽里的东西。
输入
输入有若干行： 第一行只有一个整数b（1≤b≤1000）表示区间数。 第二行至第b+1行，每行两个整数，表示一个区间，较小的端点在前。
输出
输出只有一行，该行只有一个整数，表示最多能吃到多少个槽中的食物。
就是一道动态规划（线段覆盖），题意也很好理解。
但是要注意的是，一定要按照饲料槽的顺序做。在线做法似乎是不可行的。
例如先输入后面的线段，再输入前面的线段，两者可能可同时取，但由于有几率有复杂的冲突关系而不能同时取得，如果要判冲突（然而我不会）会出一些奇奇怪怪的事情。另一方面取max又会把后面的线段覆盖掉，
所以还是离线排序或者O(max(end) + 1)扫一遍吧
ps：本题数据没有x相同。如果x有相同那么就要排序做了，否则可用f[i][]存一条线段。
upd - 12.04.2017 19:05
刚做一道“Tom的烦恼”，就是有重起点。可以二维保存线段，另加数组les[]存个数——或者动态开也是可以的。
最新文章
- MVC前台Post/Get异步获得数据时参数的取值问题
- EF with (LocalDb)V11.0
- TOMCAT配置外部应用
- 第 6 章 贴近servlet
- apache 配置多个虚拟主机，不同的端口
- 【转】bShare分享插件的使用
- git相关资料
- datagridview的某些属性以及增删改查
- LINQ——语言级集成查询入门指南(1)
- spring源码_下载以及转入eclipse （2016-11-08）
- MYSQL常用命令集合(转载)
- 关于服务器防火墙和discuz论坛的问题
- RESTEasy:@FormParam、@PathParam、@QueryParam、@HeaderParam、@CookieParam、@MatrixParam说明
- hdu Write a simple HTML Browser
- git个人学习总结
- 【Java】的四种引用的区别
- linux的可中断sleep_on函数分析
- ajax跨域名
- Android studio实现简单的CRUD
- ajax和302（转）