题目链接：Codeforces - The Bakery
看到k的数据范围，不难想到可以dp，状态方程为：dp[i][j] -> 表示以j结尾，分成i块的最大价值。转移方程也很简单：dp[i][j] = max{dp[i-1][k] + (k+1到j的种类数。)}然后可以用线段树去优化转移。怎么优化呢？当我们算分成i块的时候，分成i-1块的答案是已知的，然后我们只需要知道k+1到j的种类数。其实空间也可以压掉第一维。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=4e4+10;int dp[55][N],n,k,pre[N],pos[N],a[N];int mx[N<<2],lazy[N<<2];inline void push_up(int p){mx[p]=max(mx[p<<1],mx[p<<1|1]);}inline void push_down(int p){if(!lazy[p])return ;mx[p<<1]+=lazy[p],mx[p<<1|1]+=lazy[p];lazy[p<<1]+=lazy[p],lazy[p<<1|1]+=lazy[p];lazy[p]=0;}void build(int p,int l,int r,int lst){if(l==r){mx[p]=dp[lst][l-1];return ;}int mid=l+r>>1;build(p<<1,l,mid,lst),build(p<<1|1,mid+1,r,lst);push_up(p);}void change(int p,int l,int r,int ql,int qr,int val){if(l==ql&&r==qr){mx[p]+=val,lazy[p]+=val;return ;}int mid=l+r>>1;push_down(p);if(qr<=mid)change(p<<1,l,mid,ql,qr,val);else if(ql>mid)change(p<<1|1,mid+1,r,ql,qr,val);elsechange(p<<1,l,mid,ql,mid,val),change(p<<1|1,mid+1,r,mid+1,qr,val);push_up(p);}int ask(int p,int l,int r,int ql,int qr){if(l==ql&&r==qr)return mx[p];int mid=l+r>>1;push_down(p);if(qr<=mid)return ask(p<<1,l,mid,ql,qr);else if(ql>mid)return ask(p<<1|1,mid+1,r,ql,qr);elsereturn max(ask(p<<1,l,mid,ql,mid),ask(p<<1|1,mid+1,r,mid+1,qr));}signed main(){cin>>n>>k;for(int i=1;i<=n;i++){scanf("%d",&a[i]);pre[i]=pos[a[i]]+1;pos[a[i]]=i;}for(int i=1;i<=k;i++){build(1,1,n,i-1);memset(lazy,0,sizeof lazy);for(int j=1;j<=n;j++){change(1,1,n,pre[j],j,1);dp[i][j]=ask(1,1,n,1,j);}}cout<<dp[k][n];return 0;}
