区间DP石子合并环形

7-10 石子合并

在环形布局的运动场周围分布着 N 堆石子，现需按照一定顺序将这些石子逐步合并为一堆。合并规则为每次仅可选取两堆相邻的石子进行整合，形成新的石子堆，并将此次整合过程中所涉及的石子数量作为得分记录。

请设计一种计算方法，用以确定将全部 N 堆石子最终合并为一堆时所能获得的最小得分与最大得分。

输入格式:

输入数据的第一行包含一个正整数 N ，用于表示石子堆的总数。

第二行由 N 个整数组成，其中第 i 个整数 ai 表示对应第 i 堆石子的数量。

输出格式:

第一行展示的是最低得分数值，第二行则呈现最高得分数值。

输入样例解析

4
4 5 9 4

输出样例:

43
54

思路：分两种解法

动态规划状态转移方程优化

dp[i][j]为从位置i开始，累加j堆石子的结果

动态规划区间合并策略

(比较直接合并和k分割合并那个值是我们要的)

本题解中所采用的策略是将环形结构扩展为两倍长度的链状结构，并通过数组存储前缀和的方式，借助差值进行区间内的累加计算，此外还可以通过模运算的方式来实现环形动态规划。

    #include<bits/stdc++.h>
    using