不能移动的石子合并

资源描述做如下两个模型的石子合并，如下模型石子都不能移动出列，且合并都仅发生在相邻两堆石子中： （1）第一个模型：一行排列且相邻合并 有n堆石子A1,A2,...,An形成一行，每堆石头个数记为ai(1<=i<=n)，相邻两堆可合并，合并的分值为新堆的 石子数。求合并为一堆的最低得分和最高得分。 （2）第二个模型：一圈排列且相邻合并 有n堆石子A1,A2,...,An形成首位相连的一个环形，An和A1相邻，每堆石头个数记为ai(1<=i<=n)，相邻两堆 可合并，合并的分值为新堆的石子数。求合并为一堆的最低得分和最高得分。 例如4堆石子，每堆石子个数：9 4 4 5 若排成一行，最小分值：(4+4)+(8+5)+(9+13)=43，最大分值：(9+4)+(13+4)+(17+5)=52。 若排成圈状，最小分值：(4+4)+(8+5)+(9+13)=43，最大分值：(9+5)+(14+4)+(18+4)=54。 此题以第一模型的最低得分为例，很多同学想着采用总是从最小的相邻两堆下手的思想，认为最后获得的也就是最 低得分。但这个贪心策略是不对的。如下反例： 石子：9 4 6 1 5 贪心策略： 9 4 6 6 计分6 9 10 6 计分10 9 16 计分16 25 计分25 得分共计：6+10+16+25=57 但9 4 6 1 5 若如下方式合并： 13 6 1 5 计分13 13 6 6 计分6 13 12 计分12 25 计分25 13+6+12+25=56 或 9 4 6 6 计分6 9 4 12 计分12 13 12 计分13 25 计分25 6+12+13+25=56 后两种方式合并出的56都比贪心策略的57来的更低，因为总选择最小的相邻两堆去合并，并不能保证后续每步 都可以最小，也许这轮最小导致后续几轮分值较大。 输入格

11078.cpp
11078.exe
11078.o