lbnDP优化算法

orz hhw posted @ 2018年7月29日 00:05 in 算法学习 with tags DP 模板 单调性 , 140 阅读

发明了一个煞笔算法,然而被SMAWK血虐

一般来说,对于$g$数组转移到$f$数组的有单调性的DP方程$f_i=min\{g_j+cost(j,i)\}$,可以用分治DP的写法达到$O(n\log n)$的复杂度。

然而,对于$f$数组转移到$f$数组的有单调性的DP方程,一般只能用麻烦的二分写法,分治写法会挂掉。

我瞎搞了一种分治套分治的DP做法,步骤如下。

lbn_fast_dp(l,r)求解$[l,r]$的DP值,那么先递归处理$[l,md]$的DP值,求完后将$[l,md]$的DP值看作$g$数组,将$[md+1,r]$看作$f$数组进行单调性DP的转移。转移完后再递归处理$[md+1,r]$的DP值。

算法理论时间复杂度$O(n\log^2n)$,但实际跑起来还挺快,而且比二分的写法好写很多。

void dp(int l,int r,int _l,int _r){
	if(l>r)return;
	int md=l+r>>1,u=_l;LL mx=1e18;
	for(int i=_l;i<=_r;i++)
		if(f[i]+sqr(s[md]-s[i]-L)<mx)
			mx=f[i]+sqr(s[md]-s[i]-L),u=i;
	if(mx<f[md])f[md]=mx,to[md]=u,dp(l,md-1,_l,u);
	dp(md+1,r,u,_r);
}
void lbn_fast_dp(int l,int r){
	if(l==r)return;
	int md=l+r>>1;
	lbn_fast_dp(l,md);
	dp(md+1,r,max(l,to[md]),md);
	lbn_fast_dp(md+1,r);
}

登录 *


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