Codeforces 833B - The Bakery

Codeforces 833B - The Bakery

题意

将一段数字分成最多50个区间,每个区间的价值是区间内不同数字的个数,问怎么样分区间使得价值总和最大。

题解

$dp$加线段树。

$dp[i][j]$表示第$j$个坐标分成$i$块最大的价值。

转移方程

  • $dp[i][j] = max(dp[i][j],dp[i-1][x] + restofx)$,其中$x$是从1到$j$。

因为每次要获得剩下的x中数字不同的个数,暴力的做法是$O(n^2*k)$,

ac代码