7
14
2015
0

【斜率优化】HDU 3507

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

 

对基本公式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;
}
Category: HDU | Tags: DP 斜率优化 | Read Count: 375

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com