博客

考虑








D


P












$DP$
。令











f










i


,


j

















$f_{i,j}$
表示前








i










$i$
个盒子装前









j











$j$
个蛋糕的答案：

$$f_{i,j}=\max (f_{i-1,k}+v_{k+1,j}),k\in [1,i-1]$$

其中











v








i


,


j

















$v_{i,j}$
表示第








i










$i$
个蛋糕到第









j











$j$
个蛋糕装在同一个盒子里的权值。

但这样是








O


(





n






2







k


)










$O(n^2k)$
的，然后我们考虑用线段树优化。

先枚举








i










$i$
，更新












f










i


,


j


















$f_{i,j}$
时用线段树记录








k


∈


[


1


,


j


−


1


]










$k\in [1,j-1]$
中











f










i


−


1


,


k









+





v








k


+


1


,


j

















$f_{i-1,k} + v_{k+1,j}$
的最大值，直接更新就可以了。

时间复杂度








O


(


n


k


log




n


)










$O(nk\log n)$
。

代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 35010
#define ll long long
ll c[N<<2],p[N<<2],f[2][N];
int i,j,k,n,m,P[N],l[N],x;
bool b;
inline ll Max(ll x,ll y){
    return x<y?y:x;
}
inline void Up(int x){
    c[x]=Max(c[x<<1],c[x<<1|1]);
}
inline void Down(int x){
    c[x<<1]+=p[x];c[x<<1|1]+=p[x];
    p[x<<1]+=p[x];p[x<<1|1]+=p[x];
    p[x]=0;
}
inline void Update1(int x,int l,int r,int y,int z){
    if(l==r){
        c[x]+=z;
        return;
    }
    if(p[x])Down(x);
    int Mid=l+r>>1;
    if(y<=Mid)Update1(x<<1,l,Mid,y,z);else Update1(x<<1|1,Mid+1,r,y,z);
    Up(x);
}
inline void Update(int x,int l,int r,int L,int R){
    if(l>R||r<L)return;
    if(l>=L&&r<=R){
        c[x]++;p[x]++;
        return;
    }
    if(p[x])Down(x);
    int Mid=l+r>>1;
    Update(x<<1,l,Mid,L,R);
    Update(x<<1|1,Mid+1,r,L,R);
    Up(x);
}
int main(){
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)scanf("%d",&x),P[i]=l[x],l[x]=i;
    for(i=1;i<=k;i++,b^=1){
        memset(c,0,sizeof(c));
        memset(p,0,sizeof(p));
        for(j=1;j<=n;j++){
            Update(1,0,n,P[j],j-1);
            Update1(1,0,n,j,f[b^1][j]);
            f[b][j]=c[1];
        }
    }
    printf("%I64d\n",f[b^1][n]);
    return 0;
}