CF868F Yet Another Minimization Problem 题解

· · 题解

CF868F Yet Another Minimization Problem

前言：

但是题解区没有 bfs 做得的，而且 bfs 复杂度极易证明，所以来交一篇题解。

类似整体二分的分治方法优化决策单调性 dp。

当然你可以打表输出决策点。

证明就看这道题的题解吧，我也是看的题解。

这里说一下我的实现方式：

外层遍历 k。

对于每一层：我们还是设一个 \{l,r,ql,qr\} 表示 dp 数组下标 \in [ql,qr]，决策点一定 \in [l,r]。

设 mid=\frac{ql+qr}{2}。

然后我们暴力遍历决策点区间尝试转移 dp_{mid}，记录一个 p 表示决策点 p 可以使 dp_{mid} 最小。

由于决策单调性，dp 下标 \in [ql,mid) 的决策点一定 \in [l,p]，dp 下标 \in (mid,qr] 的决策点一定 \in [p,r]。继续分治求解即可。

边界是下标集合为空或决策点集合为空。

对于快速算一个区间的费用，可以用一个类似莫队的方法（可看成双指针）维护。

为了使复杂度正确，并且易于分析复杂度，可以使用 bfs 分治树的方法进行求解。

具体的，维护一个元素为 \{l,r,ql,qr\} 的队列，每次取出队首，还是按照上面说的方法做，但是将最后分治求解改为队列中依次加入元素 \{l,p,ql,mid-1\} 和 \{p,r,mid+1,qr\}。

发现分治树深度为 \log n，对于每一层，对答案造成贡献的区间指针一定是向右移动，所以每一层复杂度为线性。

总时间复杂度 O(kn \log n)，常数可能较大。

:::success[Code]

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar()                                                              \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt)     \
    ? EOF                                                                 \
    : *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{
    int x=0,c=getchar(),f=0;
    for(;c>'9'||c<'0';f=c=='-',c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}
inline void write(int x)
{
    if(x<0) x=-x,putchar('-');
    if(x>9)  write(x/10); 
    putchar(x%10+'0');
}

const int N=1e5+5;
int n,k;
int a[N];
int dp[N],dp2[N];

struct Node{
    int l,r,ql,qr;
    // 决策 in [l,r] ，dp数组下标 in [ql,qr];
};
int cnt[N];
queue<Node> q;
int nwl=1,nwr,res;

int calc(int l,int r)
{
    while(nwr<r) res+=cnt[a[++nwr]]++;
    while(nwl>l) res+=cnt[a[--nwl]]++;
    while(nwr>r) res-=--cnt[a[nwr--]];
    while(nwl<l) res-=--cnt[a[nwl++]];
    return res;
}

signed main()
{
    memset(dp,0x3f,sizeof(dp));
    memset(dp2,0x3f,sizeof(dp2));

    dp[0]=0;
    n=read();
    k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int iiii=1;iiii<=k;iiii++)
    {
        q.push(Node{1,n,1,n});
        while(q.size())
        {
            Node nw=q.front();
            q.pop();
            if(nw.l>nw.r||nw.ql>nw.qr) continue;
            int mid=(nw.ql+nw.qr)>>1,p=0;

            for(int i=nw.l;i<=min(nw.r,mid);i++)
            {
                int to=calc(i,mid)+dp[i-1];
                if(to<dp2[mid]) { dp2[mid]=to,p=i; }
            }
            q.push({nw.l,p,nw.ql,mid-1});
            q.push({p,nw.r,mid+1,nw.qr});
        }
        for(int j=1;j<=n;j++) dp[j]=dp2[j];
        memset(dp2,0x3f,sizeof(dp2));
    }
    cout<<dp[n]<<"\n";
    return 0;
}

:::