[bzoj5125][决策单调性分治][DP]小Q的书架

本文主要是介绍[bzoj5125][决策单调性分治][DP]小Q的书架，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

懒得抠了在这里

题解

实际上就是把区间分成若干块，每块的逆序对总和最小
朴素dp不难想到是
$$f[i][j]=min(f[k][j-1]+solve(k+1,i))$$
其中$solve(x,y)$表示x->y的逆序对数
然后似乎没有什么可以优化的地方
仔细想一想，删去一个数一定不会使逆序对增加，而显然这个f数组是有单调不减性的
所以其实他是具有决策单调性的
但是这里我们又不能直接移决策点，因为点的贡献可能是不单调的
考虑一个这样的分治
$qry(dep,l1,r1,l2,r2)$表示分成了$dep$块，其中需要贡献的点在$[l1,r1]$，决策点都在$[l2,r2]$
每次把贡献点的$mid$拿出来暴力求决策点，显然后面的都在后面， 前面的都在前面
注意这里其实不能暴力求逆序对，要像莫队那样移端点…
因为分治树中每个点会贡献一个新点，总共就多出了$nlogn$个点，复杂度就会变成$lo{g}^3$…

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{if(x<0){putchar('-');x=-x;}if(!x){putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x);putchar(' ');}
inline void pr2(LL x){write(x);putchar('\n');}
const int MAXN=40005;
const int MAXK=15;int s[MAXN],n,K;
int lowbit(int x){return x&-x;}
void change(int x,int c){if(!x)return ;for(;x<=n;x+=lowbit(x))s[x]+=c;}
int findsum(int x)
{int ret=0;for(;x>=1;x-=lowbit(x))ret+=s[x];return ret;
}LL f[MAXN][MAXK];
int a[MAXN];int L,R;
LL sum,g1,g2;
void upl(int now,int c)
{sum+=c*findsum(a[now]-1);change(a[now],c);
}
void upr(int now,int c)
{sum+=c*(findsum(n)-findsum(a[now]));change(a[now],c);
}
void turn(int l,int r)
{while(L>l)upl(--L,1);while(L<l)upl(L++,-1);while(R<r)upr(++R,1);while(R>r)upr(R--,-1);
}
void qry(int now,int l1,int r1,int l2,int r2)//状态区间  决策区间 
{if(l1>r1)return ;if(l2==r2){turn(l2+1,l1-1);for(int i=l1;i<=r1;i++){upr(++R,1);f[i][now]=f[l2][now-1]+sum;}return ;}int mid=(l1+r1)/2;int pos;turn(l2,mid);for(int i=l2;i<=min(mid,r2);i++){upl(L++,-1);if(f[mid][now]>f[i][now-1]+sum)f[mid][now]=f[i][now-1]+sum,pos=i;}qry(now,l1,mid-1,l2,pos);qry(now,mid+1,r1,pos,r2);return ;}
int main()
{n=read();K=read();for(int i=1;i<=n;i++)a[i]=read();L=0;while(R<n)upr(++R,1);memset(f,63,sizeof(f));f[0][0]=0;for(int i=1;i<=K;i++)qry(i,0,n,0,n);pr2(f[n][K]);return 0;
}

这篇关于[bzoj5125][决策单调性分治][DP]小Q的书架的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---