斜率优化板题 HDU 3507 Print Article

题目大意：输出N个数字a[N]，输出的时候可以连续的输出，每连续输出一串，它的费用是 “这串数字和的平方加上一个常数M”。n<=500000
我们设dp[i]表示输出到i的时候最少的花费，sum[i]表示从a[1]到a[i]的数字和。于是方程就是： dp[i]=dp[j]+M+(sum[i]-sum[j])^2；
很显然这个是一个二维的。题目的数字有500000个，不用试了，二维铁定超时了。那我们就来试试斜率优化吧，看看是如何做到从O(n^2)复杂度降到O(n)的。
我们假设k<j<i。如果在j的时候决策要比在k的时候决策好，那么也是就是 $dp[j]+M+(sum[i]-sum[j])^2 <= dp[k]+M+(sum[i]-sum[k])^2$ 。(因为是最小花费嘛，所以优就是小于)
两边移项一下，得到：
$(dp[j]+sum[j]^2)-(dp[k]+sum[k]^2) <= (sum[j]-sum[k])*2*sum[i]$
将 $(sum[j]-sum[k])$ 除过去，得到：
$[(dp[j]+sum[j]^2)-(dp[k]+sum[k]^2)]/(sum[j]-sum[k]) <= 2*sum[i]$
令 $x$ _i $= dp[i]-sum[i]$ ², $y$ _i $= 2*sum[i]$ .
那么不就是 $y$ _j $-y$ _k $/x$ _j $-x$ _k $<=2*sum[i]$ 么？左边是不是斜率的表示？
那么 $(y$ _j $-y$ _k $)/(x$ _j $-x$ _k $)<=2*sum[i]$ 说明了什么呢？
说明 $k[j,k]=(y$ _j $-y$ _k $)/(x$ _j $-x$ _k $)<=2*sum[i]$ 代表这j的决策比k的决策要更优。
关键的来了：若 $k<j<i$ 且 $k[i,j]<k[j,k]$ ，则j点永远不可能成为最优解，可以直接将它踢出我们的最优解集。为什么呢？
分三种情况讨论：
设当前点为a
1.如果 $k[i,j]$ 与 $k[j,k]$ 均小于 $2*sum[a]$ ，则i比j优，j比k优
2.如果 $k[i,j]$ 与 $k[j,k]$ 均大于 $2*sum[a]$ ，则k比j优，j比i优
3.如果 $k[i,j]<sum[a]$ 且 $k[i,j]>2*sum[a]$ ，则i比j优，k比j优
不论如何，j都无法成为最佳决策点，所以可以排除j
于是，所有的决策点满足一个下凸包性质
接下来看看如何找最优解。设 $k<j<i$ 。
由于我们排除了 $k[i,j]<k[j,k]$ 的情况，所以整个有效点集呈现一种下凸性质，即 $k[i,j]>k[j,k]$ 。
这样，从左到右，斜率之间就是单调递增的了。当我们的最优解取得在j点的时候，那么k点不可能再取得比j点更优的解了，于是k点也可以排除。换句话说，j点之前的点全部不可能再比j点更优了，可以全部从解集中排除。
于是对于这题我们对于斜率优化做法可以总结如下：
1.用一个单调队列来维护解集。
2.假设队列中从头到尾已经有元素a b c。那么当d要入队的时候，我们维护队列的下凸性质，即如果 $k[d,c]<=k[c,b]$ ，那么就将c点删除。直到找到 $k[d,x]>k[x,y]$ 为止，并将d点加入在该位置中。
3.找最佳决策点时，设当前求解状态为i，从队头开始，如果已有元素a b c，当i点要求解时，如果 $k[b,a]<=2*sum[i]$ ，那么说明b点比a点更优，a点可以排除，于是a出队，直到第一次遇到 $k[j,j-1]>2*sum[i]$ ，此时j-1即为最佳决策点。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int n, m, s, t, dq[MAXN];
int sum[MAXN], f[MAXN];

inline int Getup(int i, int j) { return f[i] + sum[i]*sum[i] - f[j] - sum[j]*sum[j]; } //Yi-Yj
inline int Getdown(int i, int j) { return sum[i] - sum[j]; } //Xi-Xj

int main ()
{
	int x;
	while(scanf("%d%d", &n, &m) == 2)
	{
		for(int i = 1; i <= n; i++) scanf("%d", &x), sum[i] = sum[i-1] + x;
		f[0] = 0; s = t = 0; dq[t++] = 0;
		for(int i = 1; i <= n; i++)
		{
			while(t-s > 1 && Getup(dq[s+1], dq[s])  <= sum[i] * 2 * Getdown(dq[s+1], dq[s])) s++;
			f[i] = f[dq[s]] + (sum[i] - sum[dq[s]]) * (sum[i] - sum[dq[s]]) + m;
			while(t-s > 1 && Getup(i, dq[t-1]) * Getdown(dq[t-1], dq[t-2]) <= Getup(dq[t-1], dq[t-2]) * Getdown(i, dq[t-1])) t--;
			dq[t++] = i;
		}
		printf("%d
", f[n]);
	}
}