题解 CF868F 【Yet Another Minimization Problem】
zhongyuwei
2019-01-18 21:13:14
我们设$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$的。
``` cpp
//这里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}$。答案出奇地暴力：直接用类似与莫队的那种方法，暴力挪左右端点的指针！像这样：
``` cpp
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)$的时间解决了。
完整代码：
``` cpp
#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;
}
```