Flandre Scarlet's Blog

听说是裸的斜率优化，但我还是照着标程写了一遍。

对基本公式f[i]=min{f[j]+(s[i]-s[j])^2+M}，取i的两个一般决策点j,k(j<k)，s[i]为1..i的cost总和，因为cost非负，所以s随i不减。

若k优于j，则f[k]+(s[i]-s[k])^2+M<f[j]+(s[i]-s[j])^2+M，化简得f[k]-f[j]+s[k]^2-s[j]^2<2*s[i]*(s[k]-s[j])。

由于j<k，则s[k]>s[j]，两边同除s[k]-s[j]得(f[k]-f[j]+s[k]^2-s[j]^2)/(s[k]-s[j])<2*s[i]。

方便起见,我们将左边分式的分子分母同时变号(f[j]-f[k]+s[j]^2-s[k]^2)/(s[j]-s[k])<2*s[i]。

可以看到不等式左边与i无关,右边只与i有关。 记slope[j,k]=(f[j]-f[k]+s[j]^2-s[k]^2)/(s[j]-s[k])。

结论1：

对于i的两个决策点j,k(j<k)，决策k优于决策j就等价于slope[j,k]<2*s[i]。

其实我们还可以知道，决策点k永远会比决策点j优，因为对于以后的i',s[i']>s[i]>slope[j,k]。

再来考虑三个点j,k,l(j<k<l)之间的优劣关系。

还是通过斜率:

如果slope[j,k]>slope[k,l]：

1.若slope[k,l]<2*s[i]，那么由之前的结论1，l 比k优。

2.若slope[k,l]>2*s[i]，则slope[j,k]>2*s[i]，那么由之前的结论(△),决策j不比k差。

综上，如果slope[j,k]>slope[k,l]，k是可以淘汰掉的。

结论2：

对于三个决策点j,k,l(j<k<l),如果slope[j,k]>slope[k,l],那么k永远不会成为某个点的最优决策。

根据这两个结论，用一个单调队列来剔除无用决策。

转自：http://www.cnblogs.com/xiaolongchase/archive/2012/02/10/2344769.html

CODE：

#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#define maxn 500010
#define INF 2147483647
using namespace std;
typedef long long LL;
LL sum[maxn],dp[maxn];
int Q[maxn],n,L,R,m;
int slope(int j,int k)
{
	if(sum[j]==sum[k])
		if (dp[j]>dp[k]) return -1;
		else return INF;
	return (dp[j]-dp[k]+sum[j]*sum[j]-sum[k]*sum[k])/(sum[j]-sum[k]);
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		sum[0]=0;
		for (int i=1;i<=n;i++)
		{
			scanf("%lld",&sum[i]);
			sum[i]+=sum[i-1];
		}
		L=R=0;
		for (int i=1;i<=n;i++)
		{
			while(L<R&&slope(Q[L],Q[L+1])<2*sum[i]) L++;
			dp[i]=dp[Q[L]]+(sum[i]-sum[Q[L]])*(sum[i]-sum[Q[L]])+m;
			while(L<R&&slope(Q[R-1],Q[R])>slope(Q[R],i)) R--;
			R++;
			Q[R]=i;
		}
		printf("%lld\n",dp[n]);
	}
	return 0;
}