题解 CF833B 【The Bakery】
KevinYu
2018-12-06 16:50:54
这道题是一道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;
}
```