感觉此题难啊，数学还是太渣了，看了半天的题解才算明白了点儿。
题目大意
给一个长度为n且仅由1和-1组成的序列ai, i = 1, 2, ..., n，每个位置都有另一个值vi，要求用某种方案将序列划分为m（0 < m
< n）个非空连续子序列，使得所有子序列中和的最大绝对值最小，并且在所有满足上述条件的方案中划分位置的v[i]序列字典序最小。
猜想及证明
记
、
记题目中说的和的最大绝对值的最小值为
有如下几个结论
- 若
并且
，则
- 若并且
，则
- 若
，则
证明：
- 第一条结论是显然的
- 对于第二条结论，首先可以肯定
，所以
。我们要证明对于和为零长度为n的序列，始终存在方案将其划分为i段（i = 1, 2,...,
n），且每一段的和都是-1, 0, 1中一个（即
）。这样我们就能得到。证明方法如下：
- 考虑将序列划分为n段，显然这是满足条件的，因为每一段的和都为1或-1
- 现在考虑将这n段中相邻的进行合并，由于整个序列的和为0，故一定能找到一对相邻的段，它们一个的和为-1，另一个为1，令它们合并后，新的段和为0，得到划分为n
- 1段的方案
- 继续执行合并。由于整个序列和为0，每一段的和都为-1， 0，
1，所以只要序列中存在1，就一定存在-1，且始终存在相邻或中间仅隔着0的1和-1，且0可以任意合并，所以可以一直合并下去，直到最后仅剩下一个0，即为合并成一段的方案
- 对于第三条结论，如果，我们可以肯定的是
。原因是如果每一段的和的绝对值都小于
，整个序列的和不可能为
。下面我们证明可以构造出的方案。
- 如果
，相当于把一堆大小为
的物品分成
堆，只要保证尽量平均即可
- 如果
，由于需要保证每一段非空，我们要换一种方式考虑。考虑先取出个位置，可以做到每一段和的绝对值都为1，也就是说，每一段中可一取出一个数使得剩余部分和为0，这就又变成上面的问题，已经证明对这些部分继续划分，所以
计算方案
这题思维难度很大，就算上面的结论猜到了，敢用了，想不出下面计算字典序最小的方案的算法也是没有用的。
对于并且的情况，由于有且仅有前缀和为0的位置可选，我们仅需要维护一个单调队列，对第i个划分位置入队直到后面的前缀和为0的位置不足时为止，然后取出队中最小的即可。
对于其他情形，我们当前选择的位置受上一个位置限制。假设第
个位置为
，给定另一个位置
，可以作为第
个位置当且仅当
这个就有些难。我们对每个S值维护一个单调队列，得到第个位置后，我们访问所有S值在
中的单调队列。
看起来是不是很暴力？似乎又要MLE又要TLE的样子？让我们仔细分析空间和时间复杂度，由于我们所有位置都最多入队一次，故空间复杂度为
。因为
，总共选m次，故总的时间复杂度为。
[HNOI 2013] 旅行 （数学）
原文：http://www.cnblogs.com/jasonyu/p/hnoi_2013_travel.html
