题解 CF833B 【The Bakery】
这道题是一道DP题。
先贴上我的翻译（稍微比默认翻译优美一点）:
由于这道题来自CF，我提供一下翻译:
题目大意:
Slastyona开了一个蛋糕店，她发现把蛋糕装进盒子里可以盈利，且一个盒子里装的蛋糕种类越多，就可以卖的越贵。
题目规定一个盒子的价值为其中装蛋糕的种类。
她今天需要让k个盒子中被装上蛋糕，而且她的盒子不能为空。
装的蛋糕必须是取自一个连续的区间。
Slastyona希望最大化所有蛋糕盒的总价值。帮助她确定这个可能的最大值。
输入格式:
第一行包含两个正整数n,k，分别代表蛋糕的个数和盒子的个数。
第二行包含n个正整数，第i个数代表第i个蛋糕的类别
输出格式:
一个正整数，代表盒子的总价值。
范围:
保证n∈[1，35000]且为整数，k∈[1，min(n,50)]且为整数。
保证蛋糕的总种类数∈[1，n]且为整数。翻译就到这里。
这一题其实还是挺考验思维的，本题是一个典型的分组问题,使用区间动态规划求解(算法标签上没有写动规 orz)。
我们先来定义一下f数组。
由于我们只能取连续的区间，我们不妨定义f[i][j]为在i个盒子中装下1-j的所有蛋糕时的最大价值和。
从这个定义中我们可以得出边界条件:
f[1][i]=col[1][i]其中col[i][j]代表从i->j中的颜色种类和。
为了得到状态转移方程，我们考虑一下在原有的基础上多切一刀的情况。
我们设要分的那一刀的位置为k。
那么总价值的值就为f[j-1][k]+col[i][j]。
对于每一次更新j值，枚举每一个k，取其最大值，即为所求。
最终得转移方程:f[i][j]=max{f[j-1][k]+col[i][k+1]}根据这个，我们就可以写出状态转移的程序了，这一题就结束了。
结束了就好了，只可惜n∈[1，35000]，这么做要枚举两边n，一遍k，复杂度为O(k*n^2)，会直接爆炸。
这个数据范围的话，我们需要优化掉一个log。
怎么办呢?上线段树。
在介绍这一题中线段树的写法之前，我们先探索一个东西:
哪一些点对我们的总价值是有益的呢?实际上，一个点的有价值的范围可以仅由前一个与它同颜色的点决定。
例:样例3(每一个颜色代表有效范围)
所以我们用线段树来存储区间最值，然后就可以在O(k*n*logn)的时间内做完了。
下面来过一遍算法流程:
我们先记录下每一个点的有效范围:
int main()
{
int n,k,t;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&t);
pre[i]=pos[t]+1;
pos[t]=i;
}然后对于每一个k值，我们都建立一次线段树。
for(int i=1;i<=k;i++)
{
memset(tr,0,sizeof(tr));
build(1,1,n,i);
for(int j=1;j<=n;j++)
{
update(1,pre[j],j,1);
f[i][j]=query(1,1,j);
}
}在这里面，我们发现，我们可以看作每一个颜色都可以“透过”分割线对后面的点产生影响:
注意我们的build函数中，线段树的建树过程依赖于上一次dp。
void build(int p,int l,int r,int now)
{
if(l==r)
{
tr[p].l=l;
tr[p].r=r;
tr[p].val=f[now-1][l-1];
return;
}
tr[p].l=l;
tr[p].r=r;
int mid=(l+r)>>1;
build(ls(p),l,mid,now);
build(rs(p),mid+1,r,now);
push_up(p);
}最后输出就行了。
printf("%d\n",f[k][n]);
return 0;
}完整程序:
int main()
{
int n,k,t;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&t);
pre[i]=pos[t]+1;
pos[t]=i;
}
for(int i=1;i<=k;i++)
{
memset(tr,0,sizeof(tr));
build(1,1,n,i);
for(int j=1;j<=n;j++)
{
update(1,pre[j],j,1);
f[i][j]=query(1,1,j);
}
}
printf("%d\n",f[k][n]);
return 0;
}