luogu P5574 [CmdOI2019]任务分配问题

题面传送门

显然有一个\(O(n^2klogn)\)的dp状态就是设\(f_{i,j}\)为分了\(i\)次，到了\(j\)的最小无序度，用树状数组维护一下即可。

然后把这个东西转到二维平面上看就显然有决策单调性。

但是这个转移不能直接计算所以没有办法直接决策单调性。

因为当前层不用这一层而直接用下一层，所以可以用分治法解决。

时间复杂度\(O(nklog^2n)\)

code:

#include<cstdio>
#include<cstring>
#define N 25000
#define I inline
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int n,m,k,x,y,z,dp[N+5],g[N+5],ls=1,rs,f[N+5],a[N+5],w;
I void get(int x,int y){while(x<=n) f[x]+=y,x+=x&-x;}
I int find(int x){int ans=0;while(x) ans+=f[x],x-=x&-x;return ans;}
I void change(int l,int r){
  while(l<ls) w+=find(n)-find(a[--ls]),get(a[ls],1);
  while(r>rs) w+=find(a[++rs]-1),get(a[rs],1);
  while(l>ls) w-=find(n)-find(a[ls]),get(a[ls++],-1);
  while(r<rs) w-=find(a[rs]-1),get(a[rs--],-1);
}
I void solve(int l,int r,int x,int y){
  if(x>y) return;int nowl=ls,nowr=rs,i,mid=x+y>>1,p=mid;
  for(i=min(r,mid);i>=l;i--)change(i,mid),dp[mid]>g[i-1]+w&&(dp[mid]=g[i-1]+w,p=i);
  solve(l,p,x,mid-1);solve(p,r,mid+1,y);change(nowl,nowr);
}
int main(){
  freopen("1.in","r",stdin);
  register int i,j;scanf("%d%d",&n,&k);memset(dp,0x3f,sizeof(dp));dp[0]=0;
  for(i=1;i<=n;i++) scanf("%d",&a[i]);
  for(i=1;i<=k;i++){
    for(j=1;j<=n;j++) g[j]=dp[j];solve(1,n,1,n);
  }
  printf("%d\n",dp[n]);
}