设集合 $n=i+j+k;F(n)$表示对集合n的权值（即果子重量）， $Fruit(n)$为体力耗费。
决策1$Fruit(n)=F(k)+F(i)+F(k)+F(i)+F(j)$;//先合并i，再合并j。
决策2$Fruit(n)=F(k)+F(j)+F(k)+F(i)+F(j)$;//先合并j，在合并i。
2种方式对比会发现仅含不同项F(i),F(j),只许比较i，j大小选取小的先合并便可保证从某一相同初始状态转换至相同末状态的花费最小。

数据组数好像出多了……
反正插头DP能过……

想必看完楼上们的评论，大家对这道题的算法已经饥渴难耐了，为了满足大家的兽欲，这里我给出一个简易版的证明(没有按照严格的贪心算法的证明方法走)。
设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楼的贪心算法大部分还是正确的，除了少量细节（情况一），不过我们是真男人，何必在意这些细节!

回复 @ch3coooh :
这来自于tyvj，本来是“傻子”的

对啊沙子不可数。。。

回复 @Chenyao :
我和小伙伴们都吓傻了……每个牛喜欢的棚都不一样啊这怎么容斥……少侠你可以推一下，没准真能推出来……

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

智商捉急。。。
第一道c++。。。历经万难。。。。。。
写完整个人都斯巴达了。。。。
感谢供我帮助的各位大神@Nil @cstdio @hzx @Strawberry @Cirno
虽然某些人说的一点用都没有。。。
但再次表示感谢！！！
（发现及时用c++还是不习惯空格。。）

学习丽姐的奇偶建图法

@cstdio 数学神犇这题能不能用容斥做？没google到容斥的解法。。。

哪位仁兄能提供一下历年的分数线

我愧对党，愧对祖国，第一次居然还错了。。。

好吃的STL

回复 @CH.Genius_King :
给换题库笑尿了

这题是我第一次想要怒粘代码

TMD。此等错误题目描述如此坑爹。。我换了个题库才看懂！！@闫星光

我只想问——这个s是干毛用的？

DP的时候需要枚举环长，即在每次枚举中将环上的一个点的父亲（后继）改成1，而此时我们认为环长是一个预先确定的数。例如，在题图中，我们枚举到将2挂在1上，就认为环长是2，将3挂在1上环长就是3.但这样计算出的环长并不一定是真实的环长，例如，当枚举将3挂在1上（环为123）时，DP的最优决策有可能是将2挂在1上，从而环长就是2而非3.但这并不会影响结果，因为按照环长为3计算，最终除以的数要大一些，从而结果会更小，即“在枚举到环为123时的最优决策中把2挂在1上”计算出来的R(1)一定没有“枚举到环为12时(把2挂在1上)的最优决策”的R(1)大。
另，这道题的背包不是经典01背包，不能把“对每个点分配0,1，...，M次修改机会”当做单独的物品，因为它们之中只能取一个，所以实际上是分组背包

我叫的一般这种问题，求最短路floyd就够了，这道题竟然卡n^3..

理解题意花了好久 ，，太菜，，
解就一句话：求2的个数。。。