CF833B The Bakery

LG传送门

线段树优化DP。

其实这是很久以前就应该做了的一道题，由于颓废一直咕在那里，其实还是挺不错的一道题。

先考虑\(O(n^2k)\)做法：设\(f[i][j]\)表示\(1\)到\(i\)之间分割\(j\)次得到的最大值，\(g[i][j]\)表示\(i\)到\(j\)之间不同的颜色个数。

转移就是：

但是时空都无法承受，考虑优化。

考虑使用线段树处理转移，我们不处理\(g\)数组（\(O(n^2)\)的空间开不下），对于每一个点处理它对从前一个同颜色位置到当前位置的贡献，即在线段树上把这些位置的权值\(++\)，维护一个区间最大值，转移时直接查询前缀最大值就可以了。事实上，这里的线段树只是把\(f\)和\(g\)拿来一起转移从而优化了时间复杂度，转移的本质是没有变的。

可以滚动数组（不用也没关系），具体看代码。

#include<cstdio>

#include<cctype>

#define B 1000000

#define R register

#define I inline

using namespace std;

const int S=35003,M=140003;

char buf[B],*p1,*p2;

I char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,B,stdin),p1==p2)?EOF:*p1++;}

I int rd(){

    R int f=0; R char c=gc();

    while(c<48||c>57) c=gc();

    while(c>47&&c<58) f=f*10+(c^48),c=gc();

    return f;

}

int h[S],p[S],b[M],c[M],f[S],n;

I int max(int x,int y){return x>y?x:y;}

I void upd(int k,int v){c[k]+=v,b[k]+=v;}

I void psu(int k,int p,int q){c[k]=max(c[p],c[q]);}

I void psd(int k,int p,int q){if(b[k]) upd(p,b[k]),upd(q,b[k]),b[k]=0;}

void bld(int k,int l,int r){

    b[k]=0;

    if(l==r){

        c[k]=f[l-1];

        return ;

    }

    R int p=k<<1,q=p|1,m=l+r>>1;

    bld(p,l,m),bld(q,m+1,r),psu(k,p,q);

}

void mdf(int k,int l,int r,int x,int y){

    if(x<=l&&r<=y){

        upd(k,1);

        return ;

    }

    R int p=k<<1,q=p|1,m=l+r>>1;

    psd(k,p,q);

    if(x<=m)

        mdf(p,l,m,x,y);

    if(m<y)

        mdf(q,m+1,r,x,y);

    psu(k,p,q);

}

int qry(int k,int l,int r,int x,int y){

    if(x<=l&&r<=y)

        return c[k];

    R int m=l+r>>1,p=k<<1,q=p|1,o=0;

    psd(k,p,q);

    if(x<=m)

        o=max(o,qry(p,l,m,x,y));

    if(m<y)

        o=max(o,qry(q,m+1,r,x,y));

    return o;

}

int main(){

    R int k,i,j,x;

    n=rd(),k=rd();

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

        x=rd(),p[i]=h[x]+1,h[x]=i;

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

        bld(1,1,n);

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

            mdf(1,1,n,p[j],j),f[j]=qry(1,1,n,1,j);

    }

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

    return 0;

}