【区间dp让人头痛……还是要多写些题目练手，抽空写篇博客总结一下】
这题区间dp入门题，理解区间dp或者练手都很妙
——题目链接——
（或者直接看下面）
题面
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
范围：1≤N≤100
分析
这个范围……感受到快乐了吗？
一般这种范围复杂度都超高哦~
这题是区间DP，我想看标题就知道了，如果没有学过区间DP的话……就先学吧（这个坑可能我得好久好久好久以后填）
这题四舍五入就是个模板（？）了
难点在于它是个环，不过处理起来难度也不大
我们把这个环破开复制一遍，那么它会成为一条链，就会便于 处理啦
在这个 2*n （复制过一遍）的数组上枚举 1~n 的区间就能得到这个环能组成的所有区间
然后就是区间DP的实现过程！（不懂试着看看代码，再不懂就找找博客 / 老师学一学）
转移方程式：
dpmax[j][ends]=max(dpmax[j][ends],dpmax[j][i]+dpmax[i+1][ends]+stone[ends]-stone[j-1]);
dpmin[j][ends]=min(dpmin[j][ends],dpmin[j][i]+dpmin[i+1][ends]+stone[ends]-stone[j-1]);
【 j 和 ends 是目前区间左右端点， i 是枚举的 j~ends 里的一点，用于断开区间更新dp数组】
【 stone 数组记录整段区间前缀和，便于统计数据； dpmax 和 dpmin 看名字估计也知道是干什么了吧】
放一张AC图（悄咪咪地）我知道我很菜鸡你们自己考虑看不看下面参考
代码参考
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,a[],stone[];
int dpmax[][];
int dpmin[][];
int main()
{
cin>>n;
for (int i=; i<=n; i++)
{
cin>>a[i];
}
memset(dpmax,-,sizeof(dpmax));
memset(dpmin,0x3f3f3f,sizeof(dpmin));
memset(stone,,sizeof(stone));
for (int i=; i<=n; i++)
{
stone[i]=stone[i-]+a[i];
dpmax[i][i]=;
dpmin[i][i]=;
}
for (int i=; i<=n; i++)
{
stone[i+n]=stone[i+n-]+a[i];
//stone记录前缀和，用前缀和处理比较轻松
dpmax[i+n][i+n]=;
dpmin[i+n][i+n]=;
}
//读入与初始化
for (int len=; len<=n; len++)
//len枚举区间长度
for (int j=; j+len<=*n; j++)
//j枚举区间左端点
{
int ends=j+len-;
//区间右端点
for (int i=j; i<ends; i++)
//枚举分割点
{
dpmax[j][ends]=max(dpmax[j][ends],dpmax[j][i]+dpmax[i+][ends]+stone[ends]-stone[j-]);
dpmin[j][ends]=min(dpmin[j][ends],dpmin[j][i]+dpmin[i+][ends]+stone[ends]-stone[j-]);
}
}//核心代码！！！状态转移
int ansmin=0x3f3f3f;
int ansmax=-;
for (int i=; i<=*n; i++)
{
ansmin=min(ansmin,dpmin[i][i+n-]);
//i+n-1刚好是每种区间，超级妙的思路
ansmax=max(ansmax,dpmax[i][i+n-]);
}
cout<<ansmin<<endl<<ansmax;
return ;
}
——撒花！！！！——
我是在网上找博客学的区间DP，大概是有部分参考
—>https://blog.csdn.net/qq_40772692/article/details/80183248
有问题欢迎大佬指正
到这里就结束了，感谢看完