本文共 1759 字，大约阅读时间需要 5 分钟。
传送门：
设w(l,r)为[l,r]之间不同数字的个数 于是有：f[i][j]=max(f[k][j-1]+w(k+1,i)) k∈[1,i-1] 我们可以建立线段树对其进行维护：建立一棵关于f[i][j-1]的线段树，f[i][j-1]=Query(0,i-1) 现在要将系列分成j份，w(k+1,i)相当于将[k+1,i]区间内的数对f[i][j]的贡献，将贡献加在f[k][j-1]上后就变成了f[i][j]，于是就可以枚举每个数a[i]，设last[a[i]]为这个数上一次出现的位置，那么就将[last[a[i]],i-1]这段区间都加1
#include#include #include #define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int MX = 35000 + 5;int n,m,pre[MX],now[MX];int a[MX],f[MX],maxv[MX<<2],add[MX<<2];void build(int l,int r,int rt){ add[rt]=0; if(l==r){ maxv[rt]=f[l]; return; } int m=(l+r)>>1; build(lson); build(rson);}void PushDown(int rt){ if(add[rt]){ maxv[rt<<1]+=add[rt]; maxv[rt<<1|1]+=add[rt]; add[rt<<1]+=add[rt]; add[rt<<1|1]+=add[rt]; add[rt]=0; }}void PushUP(int rt){ maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);}void update(int L,int R,int c,int l,int r,int rt){ if(L<=l&&R>=r){ maxv[rt]+=c; add[rt]+=c; return; } PushDown(rt); int m=(l+r)>>1; if(L<=m) update(L,R,c,lson); if(R>m) update(L,R,c,rson); PushUP(rt);}int query(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r) return maxv[rt]; PushDown(rt); int m=(l+r)>>1; int ret=0; if(L<=m) ret=max(ret,query(L,R,lson)); if(R>m) ret=max(ret,query(L,R,rson)); PushUP(rt); return ret;}int main(){ //freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=n;i++){ pre[i]=now[a[i]]; now[a[i]]=i; } for(int i=1;i<=m;i++){ build(0,n,1); for(int j=1;j<=n;j++){ update(pre[j],j-1,1,0,n,1); f[j]=query(0,j-1,0,n,1); } } printf("%d\n",f[n]); return 0;}
转载地址：http://dpwpn.baihongyu.com/