P5574 [CmdOI2019]任务分配问题

决策单调性 + 分治 优化 DP。

$\mathcal O(k n^2\log n)$ 是比较显然的，暴力 DP 配合树状数组即可。注意到 $w(i,j)+w(i-1,j+1)=w(i-1,j)+w(i,j+1)$ 的经典式子，想到决策单调性。因为贡献是不太好算的，于是我们尝试利用决策单调性直接分治求解，而每次贡献利用树状数组 $\mathcal O(n\log n)$ 求。最后一共求解 $k$ 次即可。时间复杂度为 $\mathcal O(kn\log ^2n)$。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10,K=15;
template<class T>
inline void read(T &x)
{
    x=0;int f=0; 
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m;
int a[N],t[N];
int f[N],g[N];
int res,tl,tr;
int lowbit(int x){return x&(-x);}
inline void add(int x,int k)
{
    for(;x<=n;x+=lowbit(x))
        t[x]+=k;
}
inline int ask(int x)
{
    int res=0;
    for(;x;x-=lowbit(x))
        res+=t[x];
    return res;
}

void calc(int l,int r)
{
    while(tl>l)tl--,res+=ask(a[tl]),add(a[tl],1);
    while(tr<r)tr++,res+=tr-tl-ask(a[tr]),add(a[tr],1);
    while(tl<l)add(a[tl],-1),res-=ask(a[tl]),tl++;
    while(tr>r)add(a[tr],-1),res-=tr-tl-ask(a[tr]),tr--;
}

void solve(int pl,int pr,int l,int r)
{
    if(l>r)return ;
    int mid=l+r>>1,pm=mid;
    for(int i=min(pr,mid-1);i>=pl;i--)
    {
        calc(i+1,mid);
        if(g[i]+res<=f[mid])f[mid]=g[i]+res,pm=i;
    }
    solve(pl,pm,l,mid-1);
    solve(pm,pr,mid+1,r);
}
int main()
{
    memset(f,0x3f,sizeof(f));
    read(n,m);
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        a[i]=n-a[i]+1;
    }
    tl=1,tr=0;
    f[0]=g[0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            g[j]=f[j];
        solve(0,n-1,1,n);
    }
    printf("%d\n",f[n]);
    return 0;
}