魔杖
【问题描述】
有一种非常珍贵的树枝，这些树枝可以用来做优质的魔杖！选择怎样的切割方式来制作魔杖非常重要，关键是一把魔杖既不能太长、又不能太短，且制作出来的魔杖不能有冲突。
佳佳得到的这些树枝在属性上完全相同。每一个树枝都有n段（用1~n编号），给定了每段的长度L[i]和每段的魔力值M[i]。单独的一段是不可以从中间切开的，你可以做的就是选择一段或连续的几段，把它们作为一个整体切下来，再用来制作魔杖。但是一根魔杖的长度不能太长——不能大于给定的值hi；也不能太短——不能小于给定的值lo。
魔杖有一个奇怪的要求：如果某一根魔杖的制作材料是另一根魔杖的一部分，则这两根魔杖之间将发生冲突。比如说树枝有三段，从左到右的长度分别为4、1、3，佳佳需要长度为4到5之间的魔杖。佳佳可以用一根树枝的前两段做出一个长度为5的魔杖，用一根树枝的后两段做出长度为4的魔杖；但他决不能用一根树枝的前两段做了魔杖后再单独使用另一根树枝的第一段做成魔杖，因为前者包含了后者的所有成分，这会导致冲突。
我们假设佳佳可以得到任意多这样的树枝。佳佳需要制作出若干个互不冲突的魔杖，使所有魔杖的魔力值之和最大。（魔杖的长度就是组成它的那些段的长度的总和，魔力值亦然）。
【文件输入】
第一行有三个用空格隔开的正整数，分别表示n、lo、hi。
第二行的n个用空格隔开的正整数就是L[1]、L[2]……L[n]。
第三行的n个用空格隔开的正整数就是M[1]、M[2]……M[n]。
【文件输出】
只用输出一个整数，表示能够获得的魔力值的最大值。
【输入样例】
6 4 5
1 3 3 2 2 1
2 3 1 4 5 2
【输出样例】
21
【样例说明】
取[1 3] [3 2] [2 2 1]做成魔杖。
得到最大权值2+3+1+4+4+5+2=21。
【数据规模】
对于30%的数据，n<=10；
对于50%的数据，n<=100；
对于100%的数据，n<=1000，lo<=hi<=2^31-1，L[i],M[i]<=100 000
题目意思十分明确：给出一个数列和每个数的权值，选择若干个互相之间不包含的子序列使得这些子序列的和在某个范围内且所选择的权值之和（被重复选择则重复计算多次）最大。
首先需要说明的是，尽管很多有关区间选择的问题都有贪心的解决方法，但这个题目并没有什么显然的贪心结论。或许大家能想到各种可能的贪心方案，但下面的例子可以推翻几乎所有的贪心方案。
试想这样一个数据:
7 1 7
1 1 1 1 1 1 1
1 1 1 1 1 1 1
在长度上，任意一段或几段都满足要求。这个数据的答案应该是16，它是由4个连续的[1 1 1 1]得到的。需要注意的是，这种分割方案并没有保证“总是选择最短的”、“总是选择最长的”、“总是选择最先满足要求的”等条件。取的区间长度只是总长度的一半，原因仅仅是因为这样可以让每一个权值尽可能被计算多次。
这个题目可以用动态规划来解决。
设f[i,j]表示（最后一根魔杖）在最后一个区间的起始点不超过i，结束点不超过j的情况下可以获得的最大值。这个状态可能是由f[i-1,j]转移过来的，也可能是由f[i,j-1]转移过来的，还有可能是将i..j选为一个新的魔杖得到的。在最后一种情况中，为了避免包含关系，前一个区间的起始点不能超过i-1，结束点不超过j-1。于是，我们得到了类似于最长公共子序列(LCS)问题的转移方程，对所有的i<=j:
f[i,j]= Max{ f[i-1,j] ,
f[i,j-1] 当i<=j-1时 ,
f[i-1,j-1] + M[j]+M[j+1]+...+M[i] 当lo<=L[j]+L[j+1]+...L[i]<=hi时 }
为了快速地得到M[j]+M[j+1]+...+M[i]与L[j]+L[j+1]+...L[i]，我们可以初始化两个数组Sm和Sl。以处理M数组为例，Sm[i]表示M[1]+M[2]+...+M[i]，需要计算M[j]+M[j+1]+...+M[i]的值时，我们只需要计算Sm[i]-Sm[j-1]就行了。处理L数组也是同样的方法。
虽然所有的M[i]的总和最多也只有10^9，但由于每个M[i]都可能被计算多次，因此最后的结果有可能超过longint。