感觉可以这么证(xia)明(gao)，
对于每个Xi Yj的交点(i,j)，可以选择先切Xi或先切Yj，且该决策不影响任何其他决策。对于当前最大值，不妨设为Xi（或Yj亦可），因为剩下的Yp1,Yp2…均小于Xi，所以对应决策均为先切Xi

贪心，排序一遍就很简单。

暴力dp出奇迹- -
似乎换种dp方式就能deque优化做到O(n)了

哔哔哔

噗...第一次交忘了n+m总和是2e4....

想必看完楼上们的评论，大家对这道题的算法已经饥渴难耐了，为了满足大家的兽欲，这里我给出一个简易版的证明(没有按照严格的贪心算法的证明方法走)。
设K为某种状态下的常数，其大小与巧克力当前状态下x，y方向上的块数大小有关。
情况1设$X_{n},X_{n+1}$为相邻位(n+1为n的第一个小于的元素)，$W_{n}$为切完第n刀后的权值和。
可知切2刀之前状态与切2到之后的状态相同，与中间决策无关。
决策1$W_{n,first}=W_{n-1}+K*(X_{n}+X_{n+1})$
决策2$W_{n,second}=W_{n-1}+K*(X_{n+1}+X{n})$
$W_{n,first}=W_{n,second}$;这种情况下两种决策效果相同。
情况2设$X_{n},Y_{m}$为相邻位(定义同上，但在这可以假设2大小关系未知)，$W_{n}$为切完第n刀后的权值和。
可知切2刀之前状态与切2到之后的状态相同，与中间决策无关。
决策1$W_{n,first}=W_{n-1}+K*(X_{n}+2*Y_{m})$等式1
决策2$W_{n,second}=W_{n-1}+K*(Y_{m}+2*X{n})$等式2
等式1与等式2同时减去相同部分得
$First=K*Y_{m}$等式3
$Second=K*X_{n}$等式4
此时可知W值与决策有关，既若使某状态下W值越小，则应先从大的切起。
对于全局的决策，可以分为数个阶段，在这里可以证明：
若$W_{n}$最优，则$W_{n-1}$最优(反证法：由于决策过程权值是确定的，若存在更优$W_{n-1}$，则$W_{n}$不为最优，与前提矛盾)
$W_{n-1}$最优且使用最优决策，则$W_{n}$最优。
由此可递推得最终可以获得最优答案(可以用类似循环不变量的东西，这个比较开放了~)
最终得到巧克力问题满足局部最优解亦是全局最优解，该贪心算法成立。
看来2楼的贪心算法大部分还是正确的，除了少量细节（情况一），不过我们是真男人，何必在意这些细节!

这道题贪心的证明不是很简单么。。。反证不等式推矛盾。。。

有谁能证明这个贪心的正确性？
不能证明正确性的贪心总是心里感觉不爽。

贪心，不管横竖，选择最大的先切（有相等无所谓，当有几个相等的最大值时，随便选一个）
完事儿，AC。