链接:Link 耗时:1.825s
这道题做的可真够久的:前前后后加起来将近有两个小时,因此当 AC 的那一刻,自己心中还是挺自豪的。
事实上,这是一道复杂一点的区间型动态规划,之所以说“复杂”,是因为它的状态转移是二维的:切蛋糕既可以横切,也可以纵切。由此我想到了分治算法:
假设一个矩形它所需要切的刀数是 f,则 f 可以由组成该矩形的小矩形的 f 值决定。
因此,这个问题具有最优子结构。由于每个状态为一个矩形,因此需要 4 个维度来记录状态(及左上、右下两个顶点)。下面是横切时的状态转移方程,纵切时同理可得:
$$ \begin{aligned} f(up, down, left, right) = &\ min\{f(up, i, left, right) \\ & + f(i, down, left, right) + right - left\},i = up + 1 .. down -1 \end{aligned} $$
|
OOPS!
A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.