Codeforces Round

传送门：https://codeforces.com/contest/1527/problem/E

当时E题没有时间写，但是20分钟足够了。当时E题没有时间写，但是20分钟足够了。

题意

将一个长为n的序列，分成k段。将一个长为n的序列，分成k段。 在每段中，对于每个数字来说，贡献为最后一次出现的位置减第一次出现的位置，即last(x)−first(x)在每段中，对于每个数字来说，贡献为最后一次出现的位置减第一次出现的位置，即last(x)−first(x)

求分成k段后，最小的总贡献。求分成k段后，最小的总贡献。

思路

n分成k段，再看看数据范围，n≤35000，k≤100，dp[n][k]n分成k段，再看看数据范围，n≤35000，k≤100，dp[n][k]

dp[n][k]表示前n个数字分成k段后的最小总贡献。dp[n][k]表示前n个数字分成k段后的最小总贡献。 那么转移方程就非常好写：那么转移方程就非常好写：

dp[i][j]=dp[i−1][k]+val[k+1][j]dp[i][j]=dp[i−1][k]+val[k+1][j] val[i][j]表示[i,j]内所有数字的贡献。val[i][j]表示[i,j]内所有数字的贡献。 很容易推出k∈[i−1,j−1]很容易推出k∈[i−1,j−1]

这样我们的复杂度为O(n2k)，是不行的，不过O(nk)是可以的，所以我们想办法消掉一个n。这样我们的复杂度为O(n2k)，是不行的，不过O(nk)是可以的，所以我们想办法消掉一个n。

因为我们的dp[i][j]都是由dp[i−1][j−1]推出来的。因为我们的dp[i][j]都是由dp[i−1][j−1]推出来的。 而我们的目的就是找到一个k使得dp[i−1][k]+val[k+1][j]最小，而k∈[i−1,j−1].而我们的目的就是找到一个k使得dp[i−1][k]+val[k+1][j]最小，而k∈[i−1,j−1]. 进而我们可以用线段树围绕k维护区间最小值，这样我们可以在log内找到这样的k进行转移。进而我们可以用线段树围绕k维护区间最小值，这样我们可以在log内找到这样的k进行转移。

假设我们当前要将第j个数字分类，则[1,前一个位置−1]的贡献都要改变，变多少呢？多j−(前一个位置)。假设我们当前要将第j个数字分类，则[1,前一个位置−1]的贡献都要改变，变多少呢？多j−(前一个位置)。

也就是修改：

1
if(from[j] != -1) modify(1, 1, from[j] - 1, j - from[j]);

查询是在[i−1,j−1]找，也就是：

1
dp[j][i] = min(dp[j - 1][i - 1], query(1, i - 1, j - 1));

最终时间复杂度为O(nklogn)

Code

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
##include "bits/stdc++.h"
using namespace std;

const ll INF = 0x3f3f3f3f;

##define lc u << 1
##define rc u << 1  1
##define mid (t[u].l + t[u].r) / 2

const int N = 3e5 + 10;
const int K = 100 + 10;
int dp[N][K];

struct Tree {
    int l, r;
    int mn;
    int tag;
}t[N << 1];

inline void push_up(int u) {
    t[u].mn = min(t[lc].mn, t[rc].mn);
}

inline void push_down(int u) {
    if(!t[u].tag) return ;
    t[lc].tag += t[u].tag;
    t[rc].tag += t[u].tag;
    t[lc].mn  += t[u].tag;
    t[rc].mn  += t[u].tag;
    t[u].tag = 0;
}

void build(int u, int l, int r, int k) {
    t[u].l = l; t[u].r = r;
    t[u].tag = 0; t[u].mn = INF;
    if(l == r) {
        t[u].mn = dp[l][k];
        return ;
    }
    int m = (l + r) / 2;
    build(lc, l, m, k);
    build(rc, m + 1, r, k);
    push_up(u);
}

void modify(int u, int ql, int qr, int val) {
    if(ql <= t[u].l && t[u].r <= qr) {
        t[u].mn += val;
        t[u].tag += val;
        return ;
    }
    push_down(u);
    if(ql <= mid) modify(lc, ql, qr, val);
    if(qr >  mid) modify(rc, ql, qr, val);
    push_up(u);
}

int query(int u, int ql, int qr) {
    if(ql <= t[u].l && t[u].r <= qr) return t[u].mn;
    push_down(u);
    int ans = INF;
    if(ql <= mid) ans = min(ans, query(lc, ql, qr));
    if(qr  > mid) ans = min(ans, query(rc, ql, qr));
    return ans;
}

void solve() {
    int n, k; cin >> n >> k;
    vector<int> a(n + 1), pre(n + 1, -1), from(n + 1);
    for(int i = 1;i <= n; i++) cin >> a[i];

    for(int i = 1;i <= n; i++) {
        dp[i][1] = dp[i - 1][1];
        from[i] = pre[a[i]];
        if(from[i] != -1) dp[i][1] += i - from[i];
        pre[a[i]] = i;
    }

    for(int i = 2;i <= k; i++) {
        build(1, 1, n, i - 1);
        for(int j = i;j <= n; j++) {
            if(from[j] != -1) modify(1, 1, from[j] - 1, j - from[j]);
            dp[j][i] = min(dp[j - 1][i - 1], query(1, i - 1, j - 1));
            // cout << j << " " << "分成" << i << "段：" << " " << dp[j][i] << endl;
        }
    }
    cout << dp[n][k] << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/05/21/codeforces-round-721-div-2-e-partition-game/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！