Codeforces 833B The bakery

31 October 2019 | duanyll | Tags: 题解 线段树

题意

将一个长度为 $n$ 的序列分为 $k$ 段, 使得总价值最大, 一段区间的价值为区间内不同数字的个数.

$n\leq35000,k\leq50$

分析

$O(n^2k)$ 的区间DP以及各种瞎搞显然(然而考试时还是写爆了).

定义 $dp[i][j]$ 表示前 i 个数分成 j 段的总价值, col表示一段区间内不同颜色数量, 容易得到 $O(n^2k)$ 的 DP 方程:

\[dp[i][j] = \max\{dp[k][j-1] + col[k+1][i], k < i\}\]

只要在转移的时候搞掉一个 $\log$ 就可以过了. 分别考虑每一个点的贡献, 设 pre[i] 是这个位置上的点上次出现的位置, 那么它贡献的区间就是 (pre[i], i]. 所以我们在最外层枚举 $k$, 每次用上一次的 DP 数组和区间的贡献值建一次线段树来为每一个 k 查询最大值, 将复杂度优化到 $O(kn\log n)$.

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

typedef long long int64;

const int MAXN = 50010;
const int INF = 0x3f3f3f3f;

#include <cctype>
#include <cstdio>

inline int read() {
    int X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}
int a[MAXN];
int last[MAXN];
int pre[MAXN];
int dp[MAXN][52];

namespace segtree {
int maxv[MAXN << 2], lazy[MAXN << 2];
void pushup(int rt) { maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]); }
void pushdown(int rt) {
    if (lazy[rt] != 0) {
        maxv[rt << 1] += lazy[rt];
        maxv[rt << 1 | 1] += lazy[rt];
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
    }
}

void build(int k, int l, int r, int rt) {
    lazy[rt] = 0;
    if (l == r) {
        maxv[rt] = dp[l - 1][k];
        return;
    }
    int mid = (l + r) >> 1;
    build(k, l, mid, rt << 1);
    build(k, mid + 1, r, rt << 1 | 1);
    pushup(rt);
}

void update(int L, int R, int val, int l, int r, int rt) {
    if (L <= l && r <= R) {
        lazy[rt] += val;
        maxv[rt] += val;
        return;
    }
    pushdown(rt);
    int mid = (l + r) >> 1;
    if (L <= mid) update(L, R, val, l, mid, rt << 1);
    if (R > mid) update(L, R, val, mid + 1, r, rt << 1 | 1);
    pushup(rt);
}

int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) {
        return maxv[rt];
    }
    pushdown(rt);
    int mid = (l + r) >> 1;
    int ans = 0;
    if (L <= mid) ans = max(ans, query(L, R, l, mid, rt << 1));
    if (R > mid) ans = max(ans, query(L, R, mid + 1, r, rt << 1 | 1));
    return ans;
}

};  // namespace segtree

int main() {
    int n = read();
    int k = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        pre[i] = last[a[i]];
        last[a[i]] = i;
    }
    for (int j = 1; j <= k; j++) {
        segtree::build(j - 1, 1, n, 1);
        for (int i = 1; i <= n; i++) {
            segtree::update(pre[i] + 1, i, 1, 1, n, 1);
            dp[i][j] = segtree::query(1, i, 1, n, 1);
        }
    }
    cout << dp[n][k] << endl;
}