区间DP 简介：

? ? ? ? 正所谓区间 DP ，就是在区间上进行 DP 。区间 DP 以区间的长度划分阶段，记录两个端点的坐标，通过合并小区间的最优解来求出大区间的最优解。

? ? ? ? 在一般的区间 DP 题目中，区间 DP 的转移依赖于枚举分割点，由此，一般的区间 DP 的时间复杂度为 O( $n^{3}$ ) 。

一维区间 DP：?

? ? ? ? 一维区间 DP 又被称为普通的区间 DP 。顾名思义，就是在一维的数组上进行区间 DP。其中，最典型的例子就是石子合并。

????????题目大意：

????????n 堆石子摆成一个环，每次选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。求：将 n 堆石子合并成 1?堆的最小得分和最大得分。

? ? ? ? 解题思路：

????????区间 DP 的经典题目，~~所以当然是用区间 DP 了。~~先考虑最小的分：先假设石子的摆放并不是环形，而是一条直线。首先，会想到要将第 l 堆石子和第 r 堆石子合并就要先将第 l ~ r 堆石子全部合并：设? $f_{l,r}$ ?为合并第 l ~ r 堆石子的最小的得分，假设区间 [ l ~ r ]最后一次合并的两区间是 [ l , k-1 ] 和 [ k , r ] ，则有状态转移方程：

???????????????????????? $f_{l,r}$ ? =?? $\min_{l<k<=r}$ ??{? $f_{l,k-1}$ ?+? $f_{k,r}$ ?} +? $\sum_{i=l}^{r}$ ?? $a^{i}$ ? ?

????????初始时：

???????????????????????? $f_{i,i}$ ?= 0 ， $f_{i,j}$ ?=?∞ ( i ≠ j )

? ? ? ? 目标状态为： $f_{1,n}$

? ? ? ? 注意：求大区间的最小得分要依赖于小区间的最小的分，故求解时需要先枚举区间的长度，再枚举区间的左端点（或右端点），最后再枚举分割点 k 。

? ? ? ? 最后，是解决石子是环形摆放的问题，可以通过将石子堆摆放成一条直线后倍长（这也是解决环形问题的一般求解方式），最终答案为：

? ? ? ? ? ? ? ? ? ? ? ? ans =? $\min_{r-l+1=n}$ ?{? $f_{l,r}$ ?}

? ? ? ? 为了方便求合并第 l ~ r 堆石子的得分，我们可以声明一个 sum 数组，用于前缀和预处理。

? ? ? ? AC 代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<cstring>
#include<queue>//头文件不解释了
using namespace std;   
int n,minl,maxl;//n是石子堆数，minl记录最小值，maxl记录最大值
int f1[300][300];//最大值
int f2[300][300];//最小值
int num[300];//记录读入的数据
int sum[300];//前缀和
int d(int i,int j)//状态转移方程
{
	return sum[j]-sum[i-1];//求合并第l~r堆石子的得分
}  
int main()//主函数
{   
    scanf("%d",&n);//读入  
    for(int i=1;i<=n+n;i++)//读入
    {  
        scanf("%d",&num[i]);//读入  
        num[i+n]=num[i];//记录倍长的部分
        sum[i]=sum[i-1]+num[i];//记录前缀和
    }  
    for(int p=1;p<n;p++)//枚举区间长度
    {  
        for(int i=1,j=i+p;(j<n+n)&&(i<n+n);i++,j=i+p)//枚举左端点和右端点
        {  
            f2[i][j]=999999999;//最小值初始化成一个较大的数  
            for(int k=i;k<j;k++)//枚举分割点
            {  
                f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+d(i,j));//最大值状态转移方程
                f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+d(i,j));//最小值状态转移方程
            }  
        }  
    }  
    minl=999999999;//最小值要初始化为一个很大的数
    for(int i=1;i<=n;i++)//求最值
    {  
        maxl=max(maxl,f1[i][i+n-1]);//求最小值
        minl=min(minl,f2[i][i+n-1]);//求最大值
    }  
    printf("%d\n%d",minl,maxl);//输出
    return 0;//完结撒花
}