vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

题解 CF868F 【Yet Another Minimization Problem】

posted on 2021-01-16 23:00:48 | under 题解 |

最暴力的做法是令 $dp_{i,j}$ 表示前 $i$ 个数分成 $j$ 段的最小费用,转移方程为 $dp_{i,j}=\min_{k=1\sim i} (dp_{k-1,j-1}+calc(k,i))$,其中 $calc(k,i)$ 表示 $a[k,i]$ 这段区间的费用。

而这个 dp 在 $j$ 不变, $i$ 向右移时显然具有决策单调性。因为如果 $i$ 往右移了一位( $i=i+1$),有 $calc(k,i+1)=calc(k,i)+\sum_{w=k}^{i}[a_{w}=a_{i+1}]$ ,也就是说 $a[k,i]$ 这段区间有多少个数和 $a_{i+1}$ 相等, $calc(k,i+1)$ 相比于 $calc(k,i)$ 就会增加多少。所以 $k$ 越靠左 $calc(k,i+1)$ 的增量就越大,如果说在 $i$ 右移一位之前决策点 $u$ 的值 $dp_{u,j-1}+calc(u,i)$就大于等于决策点 $v$ 的值 $dp_{v,j-1}+calc(v,i)(u<v)$,那在 $i$ 右移之后,两者的前一项不变,而 $calc(u,i+1)$ 的增量一定大于等于 $calc(v,i+1)$ 的增量,所以决策点 $u$ 的值仍然会大于等于决策点 $v$ 的值。综上,当 $i$ 右移时,最优决策点只可能右移不可能左移。

接着考虑利用决策单调性来减少枚举量。借鉴一下分治的思路,把 dp 的第二维放到外层,也就是先枚举段数 $k$。如果我们知道了 $[1,n]$ 这段区间的中点 $M$ 的 dp 值以及它的最优决策点 $p$,那 $[1,M]$ 这段区间的每个点的所有可能的最优决策点组成的区间(以下简称“最优决策区间”)就会缩小为 $[1,p]$,同理, $[M+1,n]$ 这段区间的最优决策区间就缩小为 $[p+1,n]$。这样递归地分治下去,最多会递归 $\log n$层。

同时,如果我们能 $O(1)$ 地计算某段区间的费用 $calc(l,r)$,那每层的复杂度就是这一层的每次递归的最优决策区间之和,也就是 $O(n)$。但问题来了,如何 $O(1)$ 地计算 $calc$ 呢?我们借鉴一下莫队的手法,做一个类莫队暴力。即:我们记录上一次计算的区间的左右端点、对应的桶、对应的 $calc$ 值,然后对于目前要计算的区间,不断地挪动上一次的区间并更新记录的信息。但这样做的复杂度如何保证呢?首先,从区间 $[L,R]$ 的最后一次计算递归到 $[L,mid]$ 的第一次计算最多会挪动 $O(R-L)$ 次。其次,同一层递归之间的区间挪动最多为 $O(n)$ 次(因为右端点和左端点都只会向右走)。这样均摊下来单次计算就是 $O(1)$ 的,故总时间复杂度为 $O(knlogn)$,轻松通过本题。

代码如下(点个赞再走吧QAQ,谢谢您!):

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }

const int N=2e5+5;
int a[N],cnt[N]={1},n,dep,l,r;
ll dp[N][25],sum;

inline ll calc(int aim_L,int aim_R){
    while(l>aim_L) sum+=cnt[a[--l]]++;
    while(r<aim_R) sum+=cnt[a[++r]]++;
    while(l<aim_L) sum-=--cnt[a[l++]];
    while(r>aim_R) sum-=--cnt[a[r--]]; 
    return sum;
}

void divi(int L,int R,int mnL,int mnR){//求区间[L,R]的dp值 且最优决策点在区间[mnL,mnR]内
    int mid=(L+R)>>1,pos,TL=max(1,mnL),TR=min(mid,mnR); 
    //printf("div(%d,%d,%d,%d) dep=%d,[TL,TR]=[%d,%d]\n",L,R,mnL,mnR,dep,TL,TR);
    ll mn=1e15;
    fo(i,TL,TR){
        //printf("F[%d,%d]=%lld\n",i,mid,calc(i,mid));
        ll val=dp[i-1][dep-1]+calc(i,mid);
        if(val<mn) mn=val,pos=i;
    }
    dp[mid][dep]=mn;
    //fo(i,TL,mid) cnt[a[i]]--;
    //printf("dp[%d][%d]=%lld,pos=%d\n",mid,dep,dp[mid][dep],pos);
    if(L==R) return;
    divi(L,mid,mnL,pos);
    divi(mid+1,R,pos,mnR);
}

int main(){
    int k;
    cin>>n>>k;
    fo(i,1,n) dp[i][0]=1e15;
    dp[0][0]=0;
    fo(i,1,n) a[i]=read();
    while(dep<=k){
        ++dep;
        divi(1,n,1,n);
    }
    cout<<dp[n][k];
    return 0;
}
/*
-------------------------------------------------
*/