题解 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;
}