Wannafly Camp 2020 Day 3F 社团管理 - 决策单调性dp，整体二分

有 \(n\) 个数构成的序列 \({a_i}\)，要将它划分为 \(k\) 段，定义每一段的权值为这段中 \((i,j) \ s.t. \ i<j,\ a_i=a_j\) 的个数，求一种划分方案，使得各段的权值和最小。 \(n \leq 10^5, k \leq min(n,20), a_i \leq n\)

设 \(f[i][j]\) 表示将 \(a_{1..j}\) 分为 \(i\) 段的最小价值，则很容易得到转移方程

\[f[i][j]=\min (f[i-1][k]+cost(k+1,j)) \ \ \ (k<j)
\]

暴力转移是 \(O(n^2 k)\)，但这里有决策单调性，即 \(p_j\) 为 \(f[i][j]\) 的最优转移点（如果有多个就取最左边的），那么对于任意 \(k<j\) 一定有 \(p_k \leq p_j\)

注：形如 \(f_i = min/max_{j=1}^{i-1} g_j + w_{i,j}\)，记 \(f_i\) 的最优决策点为 \(p_i\)，即 \(f_i\) 从 \(g_{p_i} + w_{i,p_i}\) 处转移最优，如果满足 \(p_i \leq p_{i+1}\)，则称该方程满足决策单调性

（不想证明可以先写个暴力打表然后一眼看规律）

所以我们整体二分来加速转移

考虑我们当前求解一段区间 \([l,r]\)，所有 \(f_{i,j},\ j \in [l,r]\) 的最优决策点在 \([L,R]\) 之间。

对于 \([l,r]\) 的中点 \(mid\)，可以暴力扫一遍 \([L,R]\)，找到最优决策点 \(k\)

那么由于决策单调，所有 \(f_{i,j},\ j \in [l,mid]\) 的决策则落在 \([L,k]\) 上，所有 \(f_{i,j},\ j \in [mid+1,r]\) 的决策则落在 \([k,R]\) 上

总体时间复杂度 \(O(kn \log n)\)

因为某个循环边界写宽了然后就TLE了

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1000005;

int n,m,f[N],g[N],a[N],buc[N]={1,0},cnt;

signed pl,pr;

inline void push(signed x) {

    cnt+=buc[x];

    buc[x]++;

}

inline void pop(signed x) {

    buc[x]--;

    cnt-=buc[x];

}

void trans(signed l,signed r) {

    while(l<pl) pl--, push(a[pl]);

    while(r>pr) pr++, push(a[pr]);

    while(l>pl) pop(a[pl]), pl++;

    while(r<pr) pop(a[pr]), pr--;

    //cout<<l<<" "<<r<<" "<<cnt<<endl;

}

void solve(int l,int r,int L,int R) {

    int mid=(l+r)/2;

    int mx=1e18,k=0;

    for(int i=L;i<=min(R,mid-1);i++) { //!

        trans(i+1,mid);

        if(g[i]+cnt<mx) {

            mx=g[i]+cnt;

            k=i;

        }

    }

    f[mid]=mx;

    if(l<r) {

        solve(l,(l+r)/2-1,L,k); //!

        solve((l+r)/2+1,r,k,R);

    }

}

signed main() {

    ios::sync_with_stdio(false);

    scanf("%lld%lld",&n,&m);

    for(int i=1;i<=n;i++) {

        scanf("%lld",&a[i]);

    }

    for(int i=1;i<=n;i++) {

        trans(1,i);

        f[i]=g[i]=cnt;

        //<<g[i]<<" ";

    }//cout<<endl;

    for(int i=2;i<=m;i++) {

        solve(1,n,1,n);

        for(int j=1;j<=n;j++) g[j]=f[j];

        /*for(int j=1;j<=n;j++) {

            cout<<f[j]<<" ";

        }

        cout<<endl;*/

    }

    cout<<f[n];

}

巴特西

Wannafly Camp 2020 Day 3F 社团管理 - 决策单调性dp，整体二分

最新文章

热门文章