您现在的位置是:网站首页> 内容页

分治优化决策单调性

  • 5500aaa公海
  • 2019-06-18
  • 446人已阅读
简介<!--more-->分治优化决策单调性在我们了解的DP方程中,经常会有$f[i]=sum_{max}/sum_{min}/min/max{f[j]+calc(ij)}$,并且

<!--more-->

分治优化决策单调性

在我们了解的DP方程中,经常会有$f[i]=sum_{max}/sum_{min}/min/max{f[j]+calc(ij)}$,并且calc(ij)满足四边形不等式,这种方程存在,而通常情况下,calc(ij)可以非常轻松的得出,比如说$x^q$,或者sum[i][j]又或者是什么其他的东西。但是,有些时候,我们并不能在$O(logn)/O(1)$的时间内得出,这种情况下,正常通过维护单调队列并且二分的方法就没办法完成了。

这种情况下,我们就需要考虑calc(ij)的求法了,这种时候,如果我们发现calc(ij)可以通过分治来均摊$O(nlogn)$处理出来的时候,我们就可以通过整体二分来维护决策单调性来转移,保证整体时间复杂度的正确性。

例题时间

BZOJ 5125: [Lydsy1712月赛]小Q的书架

这道题很显然,我们要将序列分成$K$段使得这$K$段的逆序对和最小。

正常DP方程,f[i][j]=f[i-1][k]+calc(k+1j)

我们发现calc(k+1j)满足$calc(ij)+calc(i-1j+1) ge calc(ij+1)+calc(i+1j)$所以这个具有决策单调性,但是,我们虽然将DP方程的时间复杂度减少到$O(nklogn)$但是,我们发现,每次计算calc(ij)还是$O(n)$的,所以总时间复杂度不变,因此,我们考虑用分治优化决策单调性。

我们考虑在整体二分的过程中,calc(ij)每一层的时间复杂度为$O(n)$,而一共$logn$层,所以时间复杂度为$O(nlogn)$,这样,在DP的同时,calc(ij)的时间复杂度也降低了,而为了维护calc(ij)需要用到树状数组求逆序对,所以总时间复杂度为$O(nklog^2n)$显然,是可以做的...

如果K出的大一点的话,我觉得可以带权二分...所以时间复杂度可以达到$O(nlogklog^2n)$,所以还可以加强加强,嗯,就是下一道考试题了!

附上代码:

#include <cstdio>#include <algorithm>#include <cstring>#include <cstdlib>#include <iostream>#include <cmath>#include <queue>#include <bitset>using namespace std#define N 40005int f[N]sum[N]g[N]nkrlrrreta[N]void fix(int xint v){for(x<Nx+=x&-x)sum[x]+=v}int find(int x){int re=0for(xx-=x&-x)re+=sum[x]return re}void get(int lint r){ while(rl<l)fix(a[rl]-1)ret-=find(a[rl++]-1) while(rl>l)fix(a[--rl]1)ret+=find(a[rl]-1) while(rr<r)fix(a[++rr]1)ret+=find(n)-find(a[rr]) while(rr>r)fix(a[rr]-1)ret-=find(n)-find(a[rr--])}void solve(int lint rint Lint R){ if(l>r)return int m=(l+r)>>1p for(int i=min(m-1R)i>=Li--) { get(i+1m) if(g[i]+ret<f[m])f[m]=g[i]+retp=i }solve(lm-1Lp)solve(m+1rpR)}int main(){ scanf("%d%d"&n&k)rr=nrl=1 for(int i=1i<=ni++)scanf("%d"&a[i])f[i]=f[i-1]+find(n)-find(a[i])fix(a[i]1)ret=f[n] for(int i=2i<=ki++) { memcpy(gfsizeof(f[0])*(n+1)) memset(f0x3fsizeof(f[0])*(n+1)) solve(1n1n) }printf("%d"f[n])}

  

文章评论

Top