纯真巨人

文章
7
资源
0
加入时间
3年2月3天

CodeForces 834D :The Bakery 线段树优化DP

传送门题意将一个长度为nnn的序列分为kkk段,使得总价值最大。一段区间的价值表示为区间内不同数字的个数。分析我们用f[i][j]f[i][j]f[i][j]表示前iii个蛋糕分配在jjj个篮子里面 的最大价值,那么不难列出状态方程f[i][j]=max(f[p][j−1]+val(p+1,i))f[i][j] = max(f[p][j - 1] + val(p + 1,i))f[i][j]=max(f[p][j−1]+val(p+1,i))所以我们需要做的就是在lognlognlogn的时间