DDOSvoid's Blog

CF 868F Yet Another Minimization Problem

发表于 更新于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/868/F

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和一个整数 $k$，现在需要将这个序列划分成 $k$ 个连续段，每个连续段的费用是其中相同元素的对数，求最小费用的和

$n\le 10^5,k\le 20$

Solution

容易得到 $dp$ 方程，$f_{i,k}=min\{f_{j,k-1}+c_{j+1,i}\}$

其中 $c_{j+1,i}$ 表示将 $[j+1,i]$ 分成一段的费用，能够发现转移方程满足决策单调性

因为 $c_{x,y}$ 没法 $O(1)$ 求，这里我们只能使用分治法，$c_{j+1,i}$ 的维护使用类似莫队的方法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#define maxn 500010
#define INF 1000000000000000000
#define ll long long 
using namespace std;

int n, k, a[maxn];

int cnt[maxn], l, r; ll sum;
inline void add(int x) { sum += cnt[x]++; }
inline void del(int x) { sum -= --cnt[x]; } 
void move(int L, int R) {
    while (r < R) add(a[++r]);
    while (l > L) add(a[--l]);
    while (r > R) del(a[r--]);
    while (l < L) del(a[l++]);
}

ll f[maxn], g[maxn]; 
void solve(int l, int r, int L, int R) { // f_i in [l, r], g_j in [L, R] 
    if (l > r) return ; int m = l + r >> 1, p = L;
    for (int i = L; i <= min(R, m - 1); ++i) {
        move(i + 1, m);
        if (g[i] + sum < f[m]) f[m] = g[i] + sum, p = i;
    }
    solve(l, m - 1, L, p); solve(m + 1, r, p, R);
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cnt[a[1]] = 1; l = r = 1; for (int i = 0; i <= n; ++i) g[i] = INF; g[0] = 0; 
    for (int i = 1; i <= k; ++i) {
        for (int j = 0; j <= n; ++j) f[j] = INF; 
        solve(1, n, 0, n - 1); 
        for (int j = 0; j <= n; ++j) g[j] = f[j]; 
    } cout << f[n] << endl; 
    return 0;
}