CF868F Yet Another Minimization Problem

2018-10-09 20:14:43


题意:把一个长度为 $n$ 的序列分成 $m$ 段,每一段的代价是区间中相同的数的对数,最小化代价和


贴一下FlashHu大佬的博客讲解

决策单调性优化 $dp$

首先有一个暴力的 $dp$

设 $f[i][j]$ 表示前 $i$ 个数分成 $j$ 段的最小代价

那么有方程: $f[i][j]=min\left\{f[k][j-1]+cost(k,i)\right\}$

用滚动数组去掉第二维,得到: $f[i]=min\left\{g[k]+cost(k,i)\right\}$


设 $f[i]$ 的最优决策点为 $p[i]$ ,可以发现 $p[i]<=p[i+1]$

所以这个转移是具有决策单调性的

那么能不能和[JSOI2011]柠檬一样用单调栈做呢

因为这里的 $cost(k,i)$ 不能 $O(1)$ 算出

所以二分单调栈的复杂度会很高


因为转移具有单调性并且离线,考虑用分治优化

设当前求解区间为 $[l,r]$ ,决策区间为 $[L,R]$

用一个桶来记录每个值在区间中出现的次数

暴力扫 $[L,min(mid,R)]$ 区间

通过计算 $f[i]+cost(i,mid)$ 找到这一段中的最优决策点 $k$

然后递归到左子问题 $(l,mid-1,L,k)$

注意这里的子问题 $[l,mid-1],[L,k]$ 和当前问题 $[L,l-1]$ 其实是一样的

所以把这一层修改过的桶和代价还原之后再递归进去

再看右子问题 $(mid+1,r,k,R)$

它需要先处理出 $[k,mid]$ 这个区间

当前是 $[L,l-1]$ ,把左右端点分别移动,处理一下桶和代价

回溯的时候再还原,因为上一层还要用

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,a[N],cnt[N];
ll f[N],g[N];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
void solve(int l,int r,int L,int R,ll sum)//求解区间[l,r],决策区间[L,R],花费sum
{
    if (l>r) return;
    int mid=(l+r)>>1,pos=min(mid,R),k=0;
    for (reg int i=l;i<=mid;i++) sum+=(cnt[a[i]]++);
    for (reg int i=L;i<=pos;i++) {sum-=(--cnt[a[i]]); if (g[mid]>f[i]+sum) g[mid]=f[i]+sum,k=i;}
    for (reg int i=L;i<=pos;i++) sum+=(cnt[a[i]]++);
    for (reg int i=l;i<=mid;i++) sum-=(--cnt[a[i]]);//还原 
    solve(l,mid-1,L,k,sum);
    for (reg int i=l;i<=mid;i++) sum+=(cnt[a[i]]++);
    for (reg int i=L;i<k;i++) sum-=(--cnt[a[i]]);
    solve(mid+1,r,k,R,sum);
    for (reg int i=L;i<k;i++) sum+=(cnt[a[i]]++);
    for (reg int i=l;i<=mid;i++) sum-=(--cnt[a[i]]);
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=n;a[i++]=read());
    for (reg int i=1;i<=n;i++) f[i]=f[i-1]+(cnt[a[i]]++);//只分成一段的代价可以直接算出 
    memset(cnt,0,sizeof(cnt));
    for (reg int i=2;i<=m;i++)
    {
        memset(g,127/3,sizeof(g));
        solve(1,n,1,n,0);
        memcpy(f,g,sizeof(g));
    }
    printf("%lld\n",f[n]);
    return 0;
}