Readme

3219.Minimum-Cost-for-Cutting-Cake-II

我们首先考虑，在所有的横切位置里面，我们会如何排序。显然，我们会优先切cost大的横切位置。因为越靠后进行的横切位置，由于中间可能隔着若干竖切，导致在该位置可能需要更多次的横切操作。所以将单次横切cost最大的放在前面，是最合算的。

同理，在所有的竖切位置里面，我们会优先选择单次操作cost大的。

接下来考虑，一个横切与一个纵切位置里相比，我们优先选择哪个。假设此时，横向已经分为了i块，纵向已经分为了j块，每个方向上都是相对于原始大小“一切到底”。我们很容易分析得到，如果方案1是先横切再竖切，引入的代价是costH*j + costV*(i+1). 反之方案2先竖切再横切的话，引入的代价是costV*i + costH*(j+1). 比较一下，当且仅当costH > costV的时候，方案1更优。

综上，我们可以得到一个推测的结论：我们只需要将所有横切与纵切的位置按照cost从大到小排序、依次切割并且“一切到底”，这样得到的总代价最小。

上述结论有一个重要的前提，就是每刀都是一切到底。那么是否存在不“一切到底”反而更优的情况呢？考虑下面

  _________C____
A |_____|B     |
  |     |      |
  |_____|______|
           D

假设按照排序后的cost，第一刀是竖切，第二刀是横切AB。那么是否该将右半边也横切掉呢？我们的顾虑是，如果在右半边存在一个竖切的位置CD，那么AB一切到底会引入两倍的竖切CD。而如果先切CD，再切AB的延长线，那么我们引入的代价是CD+AB*2. 事实上，从之前的排序过程中我们已经知道AB的代价大于CD，所以后者的方案是不如前者的。因此，我们在按照cost顺次执行切割的时候都会“一切到底”。