CodeForces - 833B The Bakery

标签：833B lazy val int tr CodeForces Bakery now dp

看题解时全程：wow

题意：给出n个数，将其按顺序分为k组，令每组的价值为该组不同的数的个数。求一种分法，使得所有组价值和最大。

解：设dp[i][j]为将前 j 个数分为 i 组时的最大价值，显然有dp[i][j]=max(dp[i-1][k]+sum[k+1...j])，sum[k+1...j]为[k+1...j]中不同数的个数。然后优化求解过程，先解决sum怎么求。设原数组为a[i]，令c[i]为区间[i, n]内不同数的个数，pre[i]为a[i]最后一次出现的位置，那么对于每一个i，c[pre[i]+1...i]+1，最终结果即为数组定义。意思是在pre[i]+1到i之间没有出现过a[i]，那么它可以对答案贡献1，并且这样做不会有重复加的情况出现。

以样例3为例：

a：　　 7 7 8 7 7 8 1 7

pre+1：1 2 1 3 5 4 1 6

index:   1 2 3 4 5 6 7 8

c：　　 3 3 3 3 3 3 2 1

然后再来看这道题。通常我们先枚举i，再枚举j，也就是一个数一个数往里加。每添加一个数j，就可以获得所有的[k+1...j]，很快乐，直接在dp[i-1]上加然后求最大值即可。区间加和求最大值的数据结构显然用线段树。注意给dp[i][k]加上c[k+1]的值，不是c[k]。

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxx 35005
#define maxn 25
#define maxm 205
#define ll long long
#define inf 1000000009
#define mod 2520
int a[maxx]={0};
int dp[55][maxx]={0};
int pre[maxx]={0},pos[maxx]={0};
struct node{
    int val,lazy;
}tr[maxx*4];
void pushup(int now){
    tr[now].val=max(tr[now*2].val,tr[now*2+1].val);
}
void pushdown(int now){
    if(!tr[now].lazy){
        return;
    }
    tr[now*2].lazy+=tr[now].lazy;
    tr[now*2+1].lazy+=tr[now].lazy;
    tr[now*2].val+=tr[now].lazy;
    tr[now*2+1].val+=tr[now].lazy;
    tr[now].lazy=0;
}
int ii;
void build(int now,int l,int r){
    if(l==r){
        tr[now].val=dp[ii][l-1];
        tr[now].lazy=0;
        return ;
    }
    tr[now].lazy=0;
    int mid=(l+r)/2;
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    pushup(now);
}
void add(int now,int l,int r,int s,int e){
    if(s<=l&&r<=e){
        tr[now].val+=1;
        tr[now].lazy+=1;
        return;
    }
    pushdown(now);
    int mid=(l+r)/2;
    if(s<=mid) add(now*2,l,mid,s,e);
    if(mid<e) add(now*2+1,mid+1,r,s,e);
    pushup(now);
}
int query(int now,int l,int r,int s,int e){
    if(s<=l&&r<=e){
        return tr[now].val;
    }
    pushdown(now);
    int mid=(l+r)/2;
    int res=0;
    if(s<=mid) res=max(res, query(now*2,l,mid,s,e));
    if(mid<e) res=max(res, query(now*2+1,mid+1,r,s,e));
    return res;
}

signed main() {
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        pre[i]=pos[a[i]]+1;
        pos[a[i]]=i;
    }
    for(int i=1;i<=k;i++){
        ii=i-1;
        build(1,1,n);
        for(int j=1;j<=n;j++){
            add(1,1,n,pre[j],j);
            dp[i][j]= query(1,1,n,1,j);
        }
    }
    printf("%d\n",dp[k][n]);
    return 0;
}
//dp[i][j] the first j th num, distribute into i blocks
//dp[i][j]=max(dp[i-1][k]+sum[k+1...j])

View Code

 

标签：833B,lazy,val,int,tr,CodeForces,Bakery,now,dp
From： https://www.cnblogs.com/capterlliar/p/16912969.html