题解 CF833B 【The Bakery】

KevinYu

2018-12-06 16:50:54

Solution

这道题是一道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的所有蛋糕时的最大价值和。 从这个定义中我们可以得出边界条件: ```cpp 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。 怎么办呢?上线段树。 在介绍这一题中线段树的写法之前,我们先探索一个东西: ```cpp 哪一些点对我们的总价值是有益的呢? ``` 实际上,一个点的有价值的范围可以仅由前一个与它同颜色的点决定。 例:样例3(每一个颜色代表有效范围) ![](https://i.loli.net/2018/12/06/5c08deb35c5fd.jpg) 所以我们用线段树来存储区间最值,然后就可以在```O(k*n*logn)```的时间内做完了。 下面来过一遍算法流程: 我们先记录下每一个点的有效范围: ```cpp 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值,我们都建立一次线段树。 ```cpp 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); } } ``` 在这里面,我们发现,我们可以看作每一个颜色都可以“透过”分割线对后面的点产生影响: ![](https://i.loli.net/2018/12/06/5c08e2c4075cc.jpg) 注意我们的build函数中,线段树的建树过程依赖于上一次dp。 ```cpp 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); } ``` 最后输出就行了。 ```cpp printf("%d\n",f[k][n]); return 0; } ``` 完整程序: ```cpp 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; } ```