【dp】饥饿的牛

普通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[]存个数——或者动态开也是可以的。
上一篇:在 Linux OpenVPN 服务端吊销客户端证书


下一篇:Spark MLlib之使用Breeze操作矩阵向量