P5574 [CmdOI2019]任务分配问题 题解

· · 题解

很容易想到动态规划。

令 f[k][i] 表示已经放了 k 个 CPU，且最后一个 CPU 负责的任务右端点为 i 的最小无序度。

那么有转移

f[k][i]=\min_{j\le i}\left\{f[k-1][j]+w(j+1,i)\right\}

其中 w(l,r) 表示闭区间内的无序度。

假设有 q<p\le j<i，并且 f[k][j]=f[k-1][p]+w(p+1,j)，即 f[k][i] 由 f[k-1][p] 转移过来，那么

\begin{aligned} f[k-1][p]+w(p+1,j)&\le f[k-1][q]+w(q+1,j)\\ w(p+1,j)-w(q+1,j)&\le f[k-1][q]-f[k-1][p] \end{aligned}

考虑在右边新增若干个数的贡献，不难发现 w(p+1,j)-w(q+1,j)\ge w(p+1,i)-w(q+1,i)，因此

\begin{aligned} w(p+1,i)-w(q+1,i)&\le f[k-1][q]-f[k-1][p]\\ f[k-1][p]+w(p+1,i)&\le f[k-1][q]+w(q+1,i) \end{aligned}

也就是说，转移具有决策单调性。

然后就可以每次用分治的方法转移了。用类似莫队的方法维护 w(l,r) 。

问题变为值域前缀（后缀同理）和。显然可以用树状数组维护，这样子的复杂度是 \mathcal O(kn\log^2 n) 的，看起来就很慢。

其实可以用可持久化块状数组的方法做到 \mathcal O(n\sqrt n) 预处理，然后 \mathcal O(1) 查询区间内小于等于某个数的个数。

预处理时，考虑加入一个数，只要对当前块的一个后缀以及后面所有块进行修改。可持久化的方式和主席树不太一样，需要对当前修改的散块建立一个真实存在的整块，它指向若干散块，其它整块指向最后真实存在的整块。

具体细节请看代码（其实我维护的是后缀和，而且这是我第一次打这玩意，打得比较难看）。

最后的复杂度是 \mathcal O(n\sqrt n+kn\log n)。

看起来快了不少，但真正打出来的跑得很慢……

#include<iostream>
#include<cstdio>
#define inf 1145141919
using namespace std;
const int N=25000,B=160,M=8000000;
int n;
int a[N+5];
int f[26][N+5];
int id[N+5],L[N/B+5],R[N/B+5];
int lf1[M+5],v1[M+5],to1[M+5];
int cnt1,lst1[B+5],num1[N+5][N/B+5];
int pl=1,pr,res;
void insert1(int k,int x){
    int now;
    for(int i=1;i<=id[n];i+=1){
        num1[k][i]=++cnt1;
        if(R[i]<=x){
            v1[cnt1]=v1[lst1[i]]+1;
            to1[cnt1]=to1[lst1[i]];
            lst1[i]=cnt1;
        }
        if(L[i]<=x&&x<R[i]){
            v1[cnt1]=v1[lst1[i]];
            lf1[now=cnt1]=cnt1+1;
            for(int j=L[i];j<=R[i];j+=1){
                if(to1[lst1[i]]) v1[++cnt1]=v1[lf1[to1[lst1[i]]]+j-L[i]];
                else v1[++cnt1]=0;
                if(j<=x) v1[cnt1]+=1;
            }
            lst1[i]=now; to1[now]=now;
        }
        if(x<L[i]){
            v1[cnt1]=v1[lst1[i]];
            to1[cnt1]=to1[lst1[i]];
            lst1[i]=cnt1;
        }
    }
    return;
}
int query1(int k,int x){
    k=num1[k][id[x]];
    int res=v1[k];
    k=to1[k];
    if(k) res+=v1[lf1[k]+x-L[id[x]]];
    return res;
}
void init(){
    for(int i=1;i<=n;i+=1){
        id[i]=(i-1)/B+1;
        if(i%B==1) L[id[i]]=i;
        R[id[i]]=max(R[id[i]],i);
    }
    for(int i=1;i<=n;i+=1) insert1(i,a[i]);
    return;
}
int calc1(int x,int l,int r){
    if(l>r) return 0;
    return query1(r,x)-query1(l-1,x);
}
int calc2(int x,int l,int r){
    if(l>r) return 0;
    return (query1(r,1)-query1(l-1,1))-(query1(r,x+1)-query1(l-1,x+1));
}
void move(int l,int r){
    while(pr<r) res+=calc2(a[pr+1],pl,pr),pr+=1;
    while(pr>r) pr-=1,res-=calc2(a[pr+1],pl,pr);
    while(pl>l) res+=calc1(a[pl-1],pl,pr),pl-=1;
    while(pl<l) pl+=1,res-=calc1(a[pl-1],pl,pr);
    return;
}
void solve(int k,int l,int r,int L,int R){
    if(l>r) return;
    int mid=l+r>>1,ans=inf,id=0;
    for(int i=min(mid-1,R);i>=L;i-=1){
        move(i+1,mid);
        if(res+f[k-1][i]<ans) ans=res+f[k-1][i],id=i;
    }
    f[k][mid]=ans;
    solve(k,l,mid-1,L,id); solve(k,mid+1,r,id,R);
    return;
}
int main(){
    int k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i+=1) scanf("%d",&a[i]);
    init();
    for(int i=1;i<=n;i+=1) f[0][i]=inf;
    for(int i=1;i<=k;i+=1) solve(i,1,n,0,n);
    printf("%d\n",f[k][n]);
    return 0;
}

Thanks~