POJ2442:Sequence 题解

思路与神奇操作

这道题我们首先会不可避免地对每一个序列进行排序。每一个序列的顶部的和就是最大和,而次大和就是 \(n-1\)个序列的最大和一个头部值最小的序列的头部值 之和。所以,我们把视野缩小一些,讨论两个序列的合并。

Continue reading →

CH1201:最大子序和题解

Solve this Problem with the Priority Queue

单调队列的主要目标其实跟单调栈的主要目标比较相似,都是在一个单调问题中,直接排除一些可以排除的答案进行运算

在本题中,我们会采用单调队列来解决。首先,我们采用前缀和来进行快速计算。然后,在前缀的前提下,我们会在本题中使用一个策略,那就是:如果有两个位置的前缀和\(sum[i]>sum[j],其中i<j\),那么处于\(i\)位置的元素对于我们来讲,是毫无用处的。原因是,如果我们要在\(m\)长度内获得和最大的子序列,对于一个这样前缀和又大、又靠前的元素,最优解绝不是由这个元素组成的。

我们来用几个代码块来简述我们的策略。

Continue reading →