题
OwO http://codeforces.com/contest/833/problem/B
解
首先读入的时候把数据读入到2 ~ n+1的位置（因为线段树处理不到0，所以后移了一格）
dp[i][j]代表处理到第i个位置为止，分j段能得到的最大值
lst[i]记录第与第i个蛋糕一样的蛋糕出现的上一个位置
则，显然dp[i][j]=min(dp[i-t][j-1]+(从i-t+1到i位置的不同种类的蛋糕个数))
记对每一段的值有贡献的点为同一段每种类型蛋糕最左边的点（比如其中一段AAFBCCDBAB，那么对这一段有贡献的B为F后面的那个B，因为他最先出现）
那么可以从小到大枚举k
每一次枚举的时候根据k-1时的dp值建一个线段树，从左往右遍历蛋糕数组，扫到第i个蛋糕的时候，线段树上第t个点表示的是上一段的右端点取t时（即这一段起点取t+1）dp[i][k]的取值，那么显然这是一个区间最大值得线段树
维护的话，扫到第i个蛋糕的时候，线段树上(lst[i],i-1)区间的值+1，因为第k-1个区间的右端点取t取(lst[i],i-1)上的点时（即第k个区间为（t+1，i），包括了第i个蛋糕，而且第i个蛋糕为该区间第一个该种蛋糕），cake[i]种类对第k个区间有贡献
查询的话，扫到第i个蛋糕的时候，查询第k-1段右节点可以选的那一段的就可以了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int M=5e4;
int dp[M][60],nowk;
int tree[M*3],tag[M*3];
void build(int rt,int li,int ri)
{
tag[rt]=0;
if(li==ri)
{
tree[rt]=dp[li][nowk];
return ;
}
int mid=(li+ri)>>1,lc=(rt<<1),rc=(rt<<1)+1;
build(lc,li,mid);
build(rc,mid+1,ri);
tree[rt]=max(tree[lc],tree[rc]);
}
void pushdown(int rt,int li,int ri)
{
if(li==ri)
{
tag[rt]=0;
return ;
}
int mid=(li+ri)>>1,lc=(rt<<1),rc=(rt<<1)+1;
tree[lc]+=tag[rt];
tree[rc]+=tag[rt];
tag[lc]+=tag[rt];
tag[rc]+=tag[rt];
tag[rt]=0;
}
void update(int rt,int li,int ri,int lq,int rq,int val) //add
{
if(lq<=li && ri<=rq)
{
tag[rt]+=val;
tree[rt]+=val;
return ;
}
int mid=(li+ri)>>1,lc=(rt<<1),rc=(rt<<1)+1;
if(tag[rt])
pushdown(rt,li,ri);
if(mid>=lq)
update(lc,li,mid,lq,rq,val);
if(mid+1<=rq)
update(rc,mid+1,ri,lq,rq,val);
tree[rt]=max(tree[lc],tree[rc]);
}
int query(int rt,int li,int ri,int lq,int rq) //get max
{
int ret=-1e9-7;
if(lq<=li && ri<=rq)
return tree[rt];
int mid=(li+ri)>>1,lc=(rt<<1),rc=(rt<<1)+1;
if(tag[rt])
pushdown(rt,li,ri);
if(mid>=lq)
ret=max(ret,query(lc,li,mid,lq,rq));
if(mid+1<=rq)
ret=max(ret,query(rc,mid+1,ri,lq,rq));
return ret;
}
int n,k;
int cake[M];
int lst[M],tmp[M];
int ans;
void init()
{
int i,j;
for(i=1;i<=n+1;i++)
tmp[i]=1;
for(i=2;i<=n+1;i++)
{
lst[i]=tmp[cake[i]];
tmp[cake[i]]=i;
}
ans=0;
memset(dp,0,sizeof(dp));
}
int main()
{
int i,j,tmp;
scanf("%d%d",&n,&k);
for(i=2;i<=n+1;i++)
scanf("%d",&cake[i]);
init();
n++;
for(i=1;i<=k;i++)
{
nowk=i-1;
build(1,1,n);
for(j=i+1;j<=n;j++)
{
update(1,1,n,lst[j],j-1,1);
tmp=query(1,1,n,i,j-1);
// cout<<tmp<<endl;
dp[j][i]=max(dp[j][i],tmp);
}
}
ans=dp[n][k];
cout<<ans<<endl;
return 0;
}