lbnDP优化算法

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

发明了一个煞笔算法,然而被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.

Avatar_small
CUB Online 说:
2022年8月02日 16:47

City Union bank is a private authorized bank in India that provides various facilities to its account holders. With the growing banking structure, change in dynamics, and number of private players entering in the banking sector of India. This will change work culture, CUB Online competitive environment, a customer also requires their banking services at their doorsteps.Gone are the days, when people used to stand in the queues for transactions, balance check, or money transfers. Therefore, like other banks in India, City union bank also provides its users with the Online banking facility.


登录 *


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