CF1527E题解

· · 题解

题解思路：

我们可以用 dp，状态转移为：

dp_{i , j} = \min\{dp_{k , j - 1} + w_{k + 1 , i}\}

但时间复杂度至少为 \mathcal{O(n^2k)}。 我们怎么用数据结构去优化呢？

  1. 我们就按 j 分层。 每次从 j - 1 的状态推出 j。 则 f_i=dp_{i , j - 1}。 而 g_i = \min(f_k + w_{k + 1 , i})。
  2. 怎么维护： 设 h_k = f_k + w_{k + 1 , i}。 当 i \to i + 1。 分两种情况：

    1.当前数没有出现过，则贡献为 0。 2.若他出现过，那么他的贡献就是加上了 i + 1 - 上一次出现的位置。

这就是前缀加以及前缀最小值。

那么我们用线段树来维护 h 数组即可。

AC CODE:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef int ll;
const int N = 35100;
int n , k;
int last[N] , pre[N] , f[N];
struct node {
    ll t;
    ll val;
}seg[N * 4];
int a[N];
void update (int id) {
    seg[id].val = min(seg[id * 2].val , seg[id * 2 + 1].val);
}
void settag (int id , int t) {
    seg[id].val = seg[id].val + t;
    seg[id].t = seg[id].t + t;
}
void pushdown (int id) {
    if (seg[id].t != 0) {//标记非空
        settag (id * 2 , seg[id].t);
        settag (id * 2 + 1 , seg[id].t);
        seg[id].t = 0;
    }
}
void build (int id , int l , int r) {
    seg[id].t = 0;
    if (l == r) {
        seg[id].val = f[l];
    }else {
        int mid = (l + r) >> 1;
        build (id * 2 , l , mid);
        build (id * 2 + 1 , mid + 1 , r);
        update (id);
    }
}
void modify (int id , int l , int r , int ql , int qr , int t) {
    if (l == ql && r == qr){ settag(id , t); return;}
    int mid = (l + r) / 2;
    pushdown (id);
    if (qr <= mid) modify (id * 2 , l , mid , ql , qr , t);
    else if (ql > mid) modify (id * 2 + 1 , mid + 1 , r , ql , qr , t);
    else {
        modify (id * 2 , l , mid , ql , mid , t);
        modify (id * 2 + 1 , mid + 1 , r, mid + 1 , qr ,t);
    }
    update (id);
}
ll query (int id , int l , int r , int ql , int qr) {
    if (l == ql && r == qr) return seg[id].val;
    int mid = (l + r) / 2;
    pushdown (id);
    if (qr <= mid) return query (id * 2 , l , mid , ql , qr);
    else if (ql > mid) return query (id * 2 + 1 , mid + 1 , r , ql , qr);
    else {
        return min(query (id * 2 , l , mid , ql , mid) , query (id * 2 + 1 , mid + 1 , r, mid + 1 , qr));
    }
}
int main() {
    scanf ("%d%d" , &n , &k);
    for (int i = 1; i <= n; ++ i) {
        scanf ("%d" , &a[i]);
        last[i] = pre[a[i]];
        pre[a[i]] = i;
    }
    f[0] = 0;
    for (int i = 1; i <= n; ++ i) f[i] = 1 << 30;
    for (int j = 1; j <= k; ++ j) {
        build (1 , 0 , n);
        for (int i = 1; i <= n; ++ i) {
            if (last[i] != 0) modify (1 , 0 , n , 0 , last[i] - 1 , i - last[i]);
            f[i] = query (1 , 0 , n , 0 , i - 1);
        }
    }   
    printf ("%d\n" , f[n]);
    return 0;
}