【题解】CF#833 B-The Bakery

　　一个非常明显的 \(nk\) dp 状态 \(f[i][k]\) 表示以 \(i\) 为第 \(k\) 段的最后一个元素时所能获得的最大代价。转移的时候枚举上一段的最后一个元素 \(j\)更新状态即可。考虑如何优化这个过程？主要的时间消耗在两个部分：一个是确定一段区间的贡献，另一个是找到最大的值。

　　这两个都是可以使用线段树来维护的，一段区间的贡献我们可以扫描线，而最大值则直接线段树维护最大值。如何滚动反而好像是最难的……想了一会儿，因为显然 memset 不可接受，然而我们可以 \(O(n)\) 建树啊……简直对自己的zz无语惹~

#include <bits/stdc++.h>

using namespace std;

#define maxn 2000000

#define maxm 40000

int n, K, ans, a[maxn], rec[maxn], last[maxn];

int f[maxm][];

int read()

{

    int x = , k = ;

    char c; c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

struct Segament_Tree

{

    int mx[maxn], mark[maxn];

    void Push_Down(int p)

    {

        mark[p << ] += mark[p], mark[p <<  | ] += mark[p];

        mx[p << ] += mark[p], mx[p <<  | ] += mark[p];

        mark[p] = ;

    }

    void Build(int p, int l, int r, int K)

    {

        if(l == r) { mark[p] = , mx[p] = f[l - ][K]; return; }

        int mid = (l + r) >> ;

        mark[p] = ;

        Build(p << , l, mid, K), Build(p <<  | , mid + , r, K);

        mx[p] = max(mx[p << ], mx[p <<  | ]);

    }

    void Update(int p, int l, int r, int L, int R, int x)

    {

        if(L <= l && R >= r) { mx[p] += x, mark[p] += x; return; }

        if(L > r || R < l) return;

        int mid = (l + r) >> ;

        Push_Down(p);

        Update(p << , l, mid, L, R, x);

        Update(p <<  | , mid + , r, L, R, x);

        mx[p] = max(mx[p << ], mx[p <<  | ]);

    }

    int Query(int p, int l, int r, int L, int R)

    {

        if(L <= l && R >= r) { return mx[p]; }

        if(L > r || R < l) return ;

        int mid = (l + r) >> ;

        Push_Down(p);

        return max(Query(p << , l, mid, L, R), Query(p <<  | , mid + , r, L, R));

    }

}T[];

int main()

{

    n = read(), K = read();

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

    {

        a[i] = read();

        last[i] = rec[a[i]], rec[a[i]] = i;

    }

    int now = , pre = ;

    for(int j = ; j <= K; j ++)

    {

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

        {

            T[pre].Update(, , n, last[i] + , i, );

            f[i][j] = T[pre].Query(, , n, , i);

        }

        T[now].Build(, , n, j);

        swap(now, pre);

    }

    printf("%d\n", f[n][K]);

    return ;

}

巴特西

【题解】CF#833 B-The Bakery

最新文章

热门文章