lbnDP优化算法

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

发明了一个煞笔算法,然而被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);
}
Avatar_small
cash back offers 说:
2019年5月27日 18:22

this website is very good for cashback site because you get cashback with shopping, which you can use on your next shopping.

Avatar_small
cash back offers 说:
2019年5月31日 18:03

This website is very good for cashback site because you get cashback with shopping, which you can use on your next shopping.

Avatar_small
commercial cleaning 说:
2021年9月02日 15:29

The position of child-rearing involves managing lots involving mess. Moms (specially housewives) are generally mostly in the heart of messy work opportunities. Sometimes these are found wiping his or her sticky fingers and also other times these are sorting by way of mental discord. For these people, the quality of calmness for quite a while tends to get painfully incredibly elusive. For these people, standard home cleaning services are generally nothing below a bonus. The moods involving moms are actually observed to switch for better, once his or her household cleanup work finishes.


登录 *


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