The Bakery题解

· · 题解

题意

将长度为 n 的序列分成 k 段，使得总价值最大。

一段区间内的价值为区间内不同数字的个数。

思路

一眼DP。\ 定义 dp_{i,j} 为将 1-j 分为 i 段的最大价值，w(i,j) 为从 i 到 j 的价值，不难列出转移方程：

dp_{i,j}=max(dp_{i-1,k}+w(k+1,j))

看起来不错，可惜时空复杂度均超。O (n^3k) 什么玩意。

我们注意到，每种颜色 i 有贡献的区间为上一个颜色 i 出现的位置 加一 到该颜色的下标。

(非常形象的图）

结合上图，可以发现，每一个颜色区间的价值都要加一，而我们查询也是区间查询，明显线段树优化DP。

我们每次枚举切割次数时，都将线段树清空并重新建树。

这里我们注意，线段树的建树是要继承上一次DP的值，所以 tr[rt].sum=f[now-1][l-1];。

于是乎，时间复杂度成功降为 O(n·k \log n)。

code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std;

#define ll long long

const int N=35005;//注意修改
const int mod=1e9+7;

int a[N];
int f[55][N];
int co[5005][5005],t[N],lst[N],xy[N];

struct tree{
    int l,r;
    int add;//懒标记
    int sum;
}tr[N<<2];

void pushup(int rt){
    tr[rt].sum=max(tr[rt<<1].sum,tr[rt<<1|1].sum);
}

void build(int rt,int l,int r,int now){
    tr[rt].l=l;
    tr[rt].r=r;
    if(l==r){
        tr[rt].sum=f[now-1][l-1];//这里与动归数组一样。
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid,now);
    build(rt<<1|1,mid+1,r,now);
    pushup(rt);
}

void pushdown(int rt){
    if(tr[rt].add==0) return;
    tr[rt<<1].add+=tr[rt].add;
    tr[rt<<1].sum+=tr[rt].add;
    tr[rt<<1|1].add+=tr[rt].add;
    tr[rt<<1|1].sum+=tr[rt].add;
    tr[rt].add=0;
}

void add(int rt,int l,int r,int k){
    if(tr[rt].l>=l&&tr[rt].r<=r){
        tr[rt].add+=k;
        tr[rt].sum+=k;
        return ;
    }
    pushdown(rt);
    int mid=(tr[rt].l+tr[rt].r)>>1;//cao
    if(l>mid) add(rt<<1|1,l,r,k);
    else if(r<=mid){
        add(rt<<1,l,r,k);
    }
    else{
        add(rt<<1,l,mid,k);
        add(rt<<1|1,mid+1,r,k);
    }
    pushup(rt);
}

int query(int rt,int l,int r){//这里查询的是最大值，而不是和！
    if(tr[rt].l==l&&tr[rt].r==r){
        return tr[rt].sum;
    }
    if(tr[rt].l==tr[rt].r) return 0;
    pushdown(rt);
    int mid=(tr[rt].l+tr[rt].r)>>1;

    if(l>mid) return query(rt<<1|1,l,r);
    else if(r<=mid){
        return query(rt<<1,l,r);
    }
    else{
        return max(query(rt<<1,l,mid),query(rt<<1|1,mid+1,r));
    }

}
int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        lst[i]=xy[a[i]]+1;//上一个此颜色的位置
        xy[a[i]]=i;
    }
    for(int i=1;i<=m;i++){
        memset(tr,0,sizeof(tr));//
        build(1,1,n,i);
        for(int j=1;j<=n;j++){
            add(1,lst[j],j,1);
            f[i][j]=query(1,1,j);

        }
    }
    cout<<f[m][n];
    return 0;

//    fclose(stdin);
//    fclose(stdout);
}

/*

 */