POJ 3709 K-Anonymous Sequence

题目大意：将一个升序的，有N个元素的序列，分组。要求每组的元素不少于K个，计算出组内各元素与最小元素的之差的和，将每组的这个值加起来，其和要最小。

N<500000，K<N

分析：

dp[i]=MIN(dp[j]+sum[i]-sum[j]-(i-j)*arr[j+1]);

令y=dp[j]+sum[i]-sum[j]+j*arr[j+1],x=arr[j+1],b=i,g=dp[i],

于是有y-bx=g

因为b值是递增的，所以有效决策点构成了下凸包。

可以用单调队列解决，又因为每组个数不能少于k个，元素进入队列时延迟k个时间单位进入。比如当前dp[i]求出，但暂缓入队，等到dp[i+k-1]求出以后再入队，然后再求dp[i+k]，此时队列中的所有元素都距离i+k至少k个元素了，所以最佳决策点只需要在队列中按照斜率关系找就行了。

另外，前k-1个元素可以不用入队，因为它们不可能做决策点。但0要入队，因为它是决策点。

这道题wa了很多次，在比较斜率的时候因为用的是乘法，所以中间结果是会溢出的,一直都没有检查出来。太粗心了。

还有这题如果把turnup改为>=返回真，就错了。按理，改为>=，凸包中会包含共线的点，但这不应该影响结果的正确性。想了很久，搞不懂什么原因，也没有找到什么好的解释。

巴特西