首页 > 编程语言 > 详细

BZOJ5125 小Q的书架(决策单调性+动态规划+分治+树状数组)

时间:2018-12-09 00:22:46      阅读:233      评论:0      收藏:0      [点我收藏+]

  设f[i][j]为前i个划成j段的最小代价,枚举上个划分点转移。容易想到这个dp有决策单调性,感性证明一下比较显然。如果用单调栈维护决策就不太能快速的求出逆序对个数了,改为使用分治,移动端点时树状数组维护即可,类似莫队的每次都在原有基础上更新。注意更新时先加再减。感觉复杂度非常玄学丝毫不能看出为啥只需要更新nlog次?

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 40010
#define M 11
#define inf 1600000010
char getc(){char c=getchar();while ((c<A||c>Z)&&(c<a||c>z)&&(c<0||c>9)) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<0||c>9) {if (c==-) f=-1;c=getchar();}
    while (c>=0&&c<=9) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
int n,m,a[N],f[M][N],tree[N],l,r,cur;
void add(int k,int x){while (k<=n) tree[k]+=x,k+=k&-k;}
int query(int k){int s=0;while (k) s+=tree[k],k-=k&-k;return s;}
void update(int L,int R)
{
    while (r<R) cur+=r-l+1-query(a[r+1]),add(a[++r],1);
    while (l>L) cur+=query(a[l-1]),add(a[--l],1);
    while (r>R) add(a[r--],-1),cur-=r-l+1-query(a[r+1]);
    while (l<L) add(a[l++],-1),cur-=query(a[l-1]);
}
void solve(int k,int x,int y,int l,int r)
{
    if (l>r) return;
    int mid=l+r>>1,id=min(mid-1,y);f[k][mid]=inf;
    for (int i=min(mid-1,y);i>=x;i--)
    {
        update(i+1,mid);
        if (f[k-1][i]+cur<=f[k][mid]) f[k][mid]=f[k-1][i]+cur,id=i;
    }
    solve(k,x,id,l,mid-1);
    solve(k,id,y,mid+1,r);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("bzoj5125.in","r",stdin);
    freopen("bzoj5125.out","w",stdout);
    const char LL[]="%I64d\n";
#else
    const char LL[]="%lld\n";
#endif
    n=read(),m=read();l=1,r=0;
    for (int i=1;i<=n;i++) a[i]=read();
    f[0][0]=0;for (int i=1;i<=n;i++) f[0][i]=inf;
    for (int j=1;j<=m;j++) solve(j,0,n-1,1,n);
    cout<<f[m][n];
    return 0;
}

 

BZOJ5125 小Q的书架(决策单调性+动态规划+分治+树状数组)

原文:https://www.cnblogs.com/Gloid/p/10089594.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!