斜率优化板题 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])2dp[j]+M+(sum[i]-sum[j])^2 <= dp[k]+M+(sum[i]-sum[k])^2dp[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](dp[j]+sum[j]^2)-(dp[k]+sum[k]^2) <= (sum[j]-sum[k])*2*sum[i](dp[j]+sum[j]2)−(dp[k]+sum[k]2)<=(sum[j]−sum[k])∗2∗sum[i]

将(sum[j]−sum[k])(sum[j]-sum[k])(sum[j]−sum[k])除过去，得到：

[(dp[j]+sum[j]2)−(dp[k]+sum[k]2)]/(sum[j]−sum[k])<=2∗sum[i][(dp[j]+sum[j]^2)-(dp[k]+sum[k]^2)]/(sum[j]-sum[k]) <= 2*sum[i][(dp[j]+sum[j]2)−(dp[k]+sum[k]2)]/(sum[j]−sum[k])<=2∗sum[i]
令xxx_i =dp[i]−sum[i]= dp[i]-sum[i]=dp[i]−sum[i]², yyy_i =2∗sum[i]= 2*sum[i]=2∗sum[i].

那么不就是yyy_j−y-y−y_k/x/x/x_j−x-x−x_k<=2∗sum[i]<=2*sum[i]<=2∗sum[i]么？左边是不是斜率的表示？

那么(y(y(y_j−y-y−y_k)/(x)/(x)/(x_j−x-x−x_k)<=2∗sum[i])<=2*sum[i])<=2∗sum[i]说明了什么呢？

说明k[j,k]=(yk[j,k]=(yk[j,k]=(y_j−y-y−y_k)/(x)/(x)/(x_j−x-x−x_k)<=2∗sum[i])<=2*sum[i])<=2∗sum[i]代表这j的决策比k的决策要更优。
关键的来了：若k<j<ik<j<ik<j<i且k[i,j]<k[j,k]k[i,j]<k[j,k]k[i,j]<k[j,k]，则j点永远不可能成为最优解，可以直接将它踢出我们的最优解集。为什么呢？

分三种情况讨论：

设当前点为a

1.如果k[i,j]k[i,j]k[i,j]与k[j,k]k[j,k]k[j,k]均小于2∗sum[a]2*sum[a]2∗sum[a]，则i比j优，j比k优

2.如果k[i,j]k[i,j]k[i,j]与k[j,k]k[j,k]k[j,k]均大于2∗sum[a]2*sum[a]2∗sum[a]，则k比j优，j比i优

3.如果k[i,j]<sum[a]k[i,j]<sum[a]k[i,j]<sum[a]且k[i,j]>2∗sum[a]k[i,j]>2*sum[a]k[i,j]>2∗sum[a]，则i比j优，k比j优

不论如何，j都无法成为最佳决策点，所以可以排除j

于是，所有的决策点满足一个下凸包性质
接下来看看如何找最优解。设k<j<ik<j<ik<j<i。

由于我们排除了k[i,j]<k[j,k]k[i,j]<k[j,k]k[i,j]<k[j,k]的情况，所以整个有效点集呈现一种下凸性质，即k[i,j]>k[j,k]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]k[d,c]<=k[c,b]k[d,c]<=k[c,b]，那么就将c点删除。直到找到k[d,x]>k[x,y]k[d,x]>k[x,y]k[d,x]>k[x,y]为止，并将d点加入在该位置中。

3.找最佳决策点时，设当前求解状态为i，从队头开始，如果已有元素a b c，当i点要求解时，如果k[b,a]<=2∗sum[i]k[b,a]<=2*sum[i]k[b,a]<=2∗sum[i]，那么说明b点比a点更优，a点可以排除，于是a出队，直到第一次遇到k[j,j−1]>2∗sum[i]k[j,j-1]>2*sum[i]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\n", f[n]);

	}

}

秒客网

斜率优化板题 HDU 3507 Print Article

相关文章