不用多说肯定是P6850
开玩笑，其实是P1880
很明显 NOI 放了一道板子题，会环形dp的可以走了。
今天来教一下大家环形dp（普及难度算法）。
区间dp
放弱化版，弱化版用的就是区间dp。
考虑dp状态： \large a_{i,j} 表示将区间 i ~ j 合并的最小值。
初始状态： 很明显 \large a_{i,i}=0 ，因为一个石子不用合并。
转移方程： 考虑枚举区间长度（我们要从小区间转移到大区间），再枚举左端点，计算右端点（ r=l+len-1 ），最后我们要把这对石子拆成两堆合并，那么枚举 k 也就是端点，状态转移方程就是把两堆加起来，再加上这一段的总和（因为这两堆合并的代价是，他们石子重量的总和）
dp_{l,r}=max(dp_{l,r},dp_{l,k}+dp_{k+1,r}+a_r-a_{l-1}) ，其中 a 数组是前缀和计算 l ~ r 的石子重量总和。
答案： dp_{1,n} 。
环形dp
考虑将数组复制一份，这样就可以断环成链（不会的，自行百度） ，答案就是从各个长度为 n 的子串中取最优值
好了这节课到此结束。
\Huge 求赞
