题解 P1714 【切蛋糕】

· · 题解

切蛋糕——题意简述

其实就是最大不定长子段和问题。

在一段长为N的数列中，找出一个长度≤M的子段，使得它的和是最大的。

但在本题中一个小细节就是子段长度也不能为0。

分析 考虑朴素写法，非常直观。

对于以第i个元素结尾的子段，最大的子段和P(i)可以表示为

P[i]=max{sum[i]-sum[j],j属于[i-M,i-1]}

于是有ans=max[P[i]]

算法的复杂度是O(NM)

在题目的范围下TLE是必然的

.

将上面P[i]的计算式改写为

P[i]=sum[i]-min{sum[j]},j属于[i-M,i-1]

显然，在每次获取P[i]的时候，Sum[i]是定值，所以P[i]由Sum[j]的最小值确定。

于是我们就要想方设法在优于O(M)的时间内实现获取最小的Sum[j]。

最优时，Sum[j]的性质：

（1）Sum[j]≤Sum[x] x∈[i-M,i-1]且x≠j

（2）j∈[i-M,i-1]

枚举加优化

考虑设计这样一个数据结构，在更低的时间复杂度内获取最优Sum[j]。

Solution 1:使用线段树，则每次用O(nlogn)的时间获取最优Sum[j]。对于本题而言，是可以通过的。但是缺点也很明显：不熟的情况下容易写错，代码可维护性不佳。

Solution 2: 引入单调队列。

所谓单调队列，我的理解是利用题目中的一些元素的单调性质，按照一定的规则组成一个单调序列。每次获取状态的时候可以在特定的位置获取状态。