两道关于动态规划的题目。。。本人愚钝实在想不出解法
1.（这题本来是关于用限制酶切割DNA的。避免麻烦我去除了生物方面的部分。。说简单一点了。。）
在一条链上有n个节点，其中有一部分是关键点，有一种切割器能截取这条链上任意两个节点之间的一段，现在总共有m种这样的切割器。问题是要求最多用k次切割器（k<m）来截到最大数量的关键点。 比如说，切割器i能切割ai到bi中间的一段，并且某关键点j在这一段上，我们就可以说这个点j被截到了。
总结一下，input是：总节点数n，切割器总数量m，可以使用切割器次数k，关键点的集合（是｛1,...,n｝的一个子集，但是并没有具体给出），每一种切割器（i=1,...,m）所能切割的两个端点ai,bi
目的是：从m种切割器里选k种，来使截到的关键点数量最大化，要求线性时间。不需要给出最后截出的关键点集合，只需要数量。
2.这题暂且叫他搬运工问题吧。
说是总共有n个位置点，一辆运货卡车停在位置0，其他每个点i都有一个重量为wi>0的大箱子，要把这些箱子按照位置点的顺序从下往上堆在卡车上。由于一个一个搬太费时间精力，所以要找出一个好办法。 假设把重量为w的箱子从a点搬到b点的cost是 c(x,y,w), 当w>w'的时候，c(x,y,w)>c(x,y,w'), 三角不等式也成立:c(x,y,w)+c(y,z,w)>=c(x,z,w)。可以一次抱着几个箱子走。不抱箱子的时候可任意行走于各个位置点不用cost。
由于不能把堆好的箱子重新排序，所以只有相邻的两个箱子可以堆一起，但是每个位置点可以放无限堆，比如说箱子3可以堆到箱子2上，但是如果要把箱子3拿到位置点1，就只能放在箱子1边上而不能堆叠。另外c(x,y,w1)+c(x,y,w2)不等于c(x,y,w1+w2)，注意，不等于。 要求就是在cost最小的情况下把所有箱子按照他们所在位置的顺序从下往上堆在卡车上，只要求出cost，具体路线不需要。
哪位能给我点思路。。。谢谢了。。。
[解决办法]
第二题还没看明白，只说第一题吧！
第一题：每个切割器可以多次使用么？否则这个K个几乎没有意义！并且应该做不到线性时间，怎么也需要排个序。如果只能用1次的话，应该用不上DP，有两个思路，1、肯定可以转为二分图匹配问题，肯定可以求得正确的解。2、用贪心，把关键点和切割区间排序后，从左到右扫描，每扫到一个点，尽量选用可以切割该点，并且切割的结束区间靠前的切割器来切割该点，这样应该是可以的，没有太仔细想。
[解决办法]
问题1线性不可能吧，直观复杂度为O(knlogn)，斜率优化应该可以优化到O(nk)(猜测)，状态就是dp[i][j]表示位置到i用了j次切割的最优。
问题2本质就是石子合并，dp[i][j]来描述区间问题，且该区间性质满足四边形法则，可以优化到O(n^2),有左偏树可以优化到O(nlogn)
