题解 CF868F 【Yet Another Minimization Problem】

· · 题解

我们设dp_{i,j}表示将序列的前i个数划分成j段所需要的最小费用，设w_{l,r}表示将l到r划分成一段所需要的花费。那么显然有转移方程：dp_{i,j} =min(dp_{x,j-1}+w_{x+1,i}) \text{ for }0\le x < i 。

而这个dp转移是具有决策单调性的。也就是说，\forall i_1 < i_2，假设它们分别是从x_1,x_2转移过来的，那么一定有x_1\le x_2。怎么证明呢？假设x_1>x_2， 那么由于x_1,x_2分别为i_1,i_2的决策点，一定有：dp_{x_1,j-1}+ w_{x_1+1,i_1}\le dp_{x_2,j-1} + w_{x_2+1,i_1}，dp_{x_2,j-1} +w_{x_2+1,i_2} \le dp_{x_1,j-1} +w_{x_1+1,i_2}。

如果dp_{x_1,j-1}+ w_{x_1+1,i_1} = dp_{x_2,j-1} + w_{x_2+1,i_1}且dp_{x_2,j-1} +w_{x_2+1,i_2} = dp_{x_1,j-1} +w_{x_1+1,i_2}，那么我们可以直接交换x_1,x_2两个决策点，决策单调性是成立的。

否则，这两个式子里面至少有一个取了小于符号。不妨假设是这样的：dp_{x_1,j-1}+ w_{x_1+1,i_1}\le dp_{x_2,j-1} + w_{x_2+1,i_1}，dp_{x_2,j-1} +w_{x_2+1,i_2} < dp_{x_1,j-1} +w_{x_1+1,i_2}。

移项可以得到：w_{x_1+1,i_1}-w_{x_2+1,i_1}\le dp_{x_2,j-1} - dp_{x_1,j-1}，w_{x_1+1,i_2} - w_{x_2+1,i_2} > dp_{x_2,j-1} - dp_{x_1,j-1}。

也就是w_{x_1+1,i_1} -w_{x_2+1,i_1} < w_{x_1+1,i_2} - w_{x_2+1,i_2}，即w_{x_2+1,i_1}-w_{x_1+1,i_1} > w_{x_2+1,i_2} - w_{x_1+1,i_2}。这个式子是显然错误的，因为在区间的增加一个元素，它对答案的贡献是与这个区间内与它值相同的元素的数量相关的。固定右端点，左端点从x_1挪到x_2时答案的增量，右端点更靠右的一定更大。决策单调性得证。

接下来，我们可以利用决策单调性，将每一次转移的枚举量尽量减少。如果最先计算整个序列中间的那个点的转移，那么计算左右两半边的枚举量都可以减半。这样分治下去，每一层计算的复杂度是与整个序列的长度线性相关的。尽管对于mid，决策点不一定在靠近中间的地方，将“可能做决策的区间”划分给左右儿子时不一定是均匀的，但是，每一层的总复杂度，是与这一层所有区间的“可能做决策区间的长度”的和线性相关，这个和一定是与序列长度线性相关的。所以这里分治的复杂度是n\log n的。

//这里l,r表示要计算[l,r]的dp值，[lb,rb]是决策点可能存在的区间
void solve(int lb,int rb,int l,int r)
{
    if(lb>rb||l>r) return; int mid=l+r>>1;
    int d=0; ll res=1e18;
    for(int i=lb;i<=rb;++i)
    {
        ll tmp=cal(i+1,mid);
        if(res>dp[cur-1][i]+tmp) res=dp[cur-1][i]+tmp,d=i;
    }
    dp[cur][mid]=res;
    solve(lb,d,l,mid-1),solve(d,rb,mid+1,r);
}

还有一个问题需要解决：如何计算w_{l,r}。答案出奇地暴力：直接用类似与莫队的那种方法，暴力挪左右端点的指针！像这样：

int buc[N],L,R,a[N];
ll ans;
void update(int c,int d){ans+=d*buc[c]*(ll)(buc[c]-1)/2;}
ll cal(int l,int r)
{
    while(L<l) update(a[L],-1),buc[a[L]]--,update(a[L],1),L++;
    while(L>l) L--,update(a[L],-1),buc[a[L]]++,update(a[L],1);
    while(R<r) R++,update(a[R],-1),buc[a[R]]++,update(a[R],1);
    while(R>r) update(a[R],-1),buc[a[R]]--,update(a[R],1),R--;
    return ans;
}

实际上，左右端点的总移动距离是O(n\log n)的。这个结论的证明可以考虑一种放缩，我们考虑让左右端点先从父亲区间它所在的位置移到左儿子区间它所在的位置，分治完左儿子之后再移回父亲区间它所在的位置，然后再移到分治右儿子的时候它所在的位置。那么显然对于每一层，指针的移动次数是O(n)的，所以总复杂度是O(n\log n)的。

至此，这道题就在O(kn\log n)的时间解决了。

完整代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
template <class T>
inline void read(T &x)
{
    x=0; char c=getchar(); int f=1;
    while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
    while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=1e5+10;
int buc[N],L,R,a[N];
ll ans;
void update(int c,int d){ans+=d*buc[c]*(ll)(buc[c]-1)/2;}
ll cal(int l,int r)
{
    while(L<l) update(a[L],-1),buc[a[L]]--,update(a[L],1),L++;
    while(L>l) L--,update(a[L],-1),buc[a[L]]++,update(a[L],1);
    while(R<r) R++,update(a[R],-1),buc[a[R]]++,update(a[R],1);
    while(R>r) update(a[R],-1),buc[a[R]]--,update(a[R],1),R--;
    return ans;
}
ll dp[22][N]; int cur;
void solve(int lb,int rb,int l,int r)
{
    if(lb>rb||l>r) return; int mid=l+r>>1;
    int d=0; ll res=1e18;
    for(int i=lb;i<=rb;++i)
    {
        ll tmp=cal(i+1,mid);
        if(res>dp[cur-1][i]+tmp) res=dp[cur-1][i]+tmp,d=i;
    }
    dp[cur][mid]=res;
    solve(lb,d,l,mid-1),solve(d,rb,mid+1,r);
}
int main()
{
    memset(dp,0x3f,sizeof(dp)); dp[0][0]=0;
    int n,m; read(n),read(m);
    for(int i=1;i<=n;++i) read(a[i]); buc[a[1]]++,L=R=1;
    for(cur=1;cur<=m;++cur) solve(0,n-1,1,n);
    printf("%lld",dp[m][n]);
    return 0;
}