题意（形式化）
有 nnn 个数排成一排，第 iii 个是 aia_iai ，每次选择两个相邻的数合并，例如选择了 aia_iai 和 ai+1a_{i+1}ai+1 ，那么将会用一个数 ai+ai+1a_i + a_{i + 1}ai +ai+1 代替原来的 aia_iai 和 ai+1a_{i+1}ai+1 ，这个操作花费为 a1+ai+1a_1+a_{i+1}a1 +ai+1 。问经过数次操作后只剩下一个数时，这个花费的最小值是多少。
思路
对于最小花费或者最大花费的问题一般使用 dp 解决，这里考虑区间 dp。
设 dpi,jdp_{i,j}dpi,j 为从第 iii 个史莱姆到第 jjj 个史莱姆这个区间合并成一个史莱姆的最小花费。
显然易见，每个区间合并后其史莱姆大小是固定的，一定为该区间总和，故在合并两个史莱姆使其合并成一个区建从 iii 到 jjj 的史莱姆时，一定为 ∑k=ijak\sum_{k=i}^{j} a_k∑k=ij ak 。既然每次合并的花费都是固定的，那么转移方程就很明显了，枚举一个区间的分割线，算出被分割后两个区间的总花费最小值后加上 ∑k=ijak\sum_{k=i}^{j} a_k∑k=ij ak 即可。
dpi,j=mini≤k<j(dpi,k+dpk+1,j+∑t=ijat)dp_{i , j} = \min_{i \le k < j} \left( dp_{i , k} + dp_{k + 1 , j} + \sum_{t=i}^{j} a_t \right) dpi,j =i≤k<jmin (dpi,k +dpk+1,j +t=i∑j at )
而初始状态则是范围为一个史莱姆，一次都不用合并的情况，花费为 000。
dpi,i=0,1≤i≤ndp_{i,i} = 0,\quad 1 \le i \le n dpi,i =0,1≤i≤n
当然求和部分可以用时前缀和优化。
实际上本体就是 P1775 石子合并（弱化版） 把范围改大了点而已，算是二倍经验。
