codeforces 834 D. The Bakery(dp + 线段树优化)

题意：

给一个长度为n的序列分成k段,每段的值为这一段不同数字的个数,最大化划分k端的值

$n <= 35000 k <= min(n,50)$

思路:

由于k比较小，直接dp就好了

$dp[i][j]$选了k段到j的最大值

$dp[i][j] = max(dp[i-1][k]+diff(k+1,j)) (0 <= k < j)$

然后用线段树优化一下, 一个数的贡献是上一个相同数字+1的位置到当前位置

#include<bits/stdc++.h>

#define LL long long

#define P pair<int,int>

#define ls(i) seg[i].lc

#define rs(i) seg[i].rc

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define ls rt<<1

#define rs (rt<<1|1)

using namespace std;

const int N = 4e4 + 10;

int read(){

    int x = 0;

    char c = getchar();

    while(c < '0' || c > '9') c = getchar();

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

    return x;

}

int n,k;

int a[N],pre[N],last[N];

int dp[55][N];

int col[N<<2],mx[N<<2];

void pushup(int rt){

    mx[rt] = max(mx[ls],mx[rs]);

}

void pushdown(int rt){

    if(col[rt]){

        col[ls] += col[rt],col[rs] += col[rt];

        mx[rs] += col[rt],mx[ls] += col[rt];

        col[rt] = 0;

    }

}

void update(int L,int R,int v,int l,int r,int rt){

    if(L <= l &&  R >= r){

        mx[rt] += v;

        col[rt] += v;

        return ;

    }

    pushdown(rt);

    int m = l + r>>1;

    if(L <= m) update(L,R,v,lson);

    if(R > m) update(L,R,v,rson);

    pushup(rt);

}

int query(int L,int R,int l,int r,int rt){

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

    pushdown(rt);

    int ans = 0;

    int m = l +r >>1;

    if(L <= m) ans = max(ans,query(L,R,lson));

    if(R > m) ans = max(ans,query(L,R,rson));

    return ans;

}

int main(){

    n = read(),k = read();

    for(int i = 2;i <= n + 1;i++){

        scanf("%d",a + i);

        pre[i] = last[a[i]];

        if(pre[i] == 0) pre[i] = 1;

        last[a[i]] = i;

    }

    for(int i = 1;i <= k;i++){

        for(int j = 2;j <= n + 1;j++){

            update(pre[j],j-1,1,1,n+1,1);

            dp[i][j] = query(pre[j],j-1,1,n+1,1);

        }

        for(int k = 1;k <= ((n+1)<<2);k++) mx[k] = col[k] = 0;

        for(int j = 1;j <= n + 1;j++){

            update(j,j,dp[i][j],1,n+1,1);

        }

    }

    int ans = 0;

    for(int j = 1;j <= n + 1;j++) ans = max(ans,dp[k][j]);

    cout<<ans<<endl;

    return 0;

}

巴特西

codeforces 834 D. The Bakery

codeforces 834 D. The Bakery(dp + 线段树优化)

题意：

思路:

最新文章

热门文章