目录

282. 石子合并

区间dp常用模板

320. 能量项链 - 区间合并dp

282. 石子合并

活动 - AcWing 

题目：

• 每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆
• 每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同
• 例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1、2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24
• 如果第二步是先合并 2、3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22
• 找出一种合理的方法，使总的代价最小，输出最小代价

思路：

定义f[i][j]为将【i,j】这一段石子合并成一堆的方案的最小代价

i是左端点，j是右端点

• 当i
• 当i==j时，只有一段石子，则代价为0

区间dp常用模板

所有的区间dp问题枚举时，第一维通常是枚举区间长度，len=1时，只有1堆，代价为0

因此枚举从 len = 2 开始；第二维枚举左端点 i （右端点 j 自动获得，j = i + len - 1） 

for(int len=1;len<=n;len++) //枚举长度
{for(int i=1;i+len-1<=n;i++) //枚举左端点{int j=i+len-1; //得到右端点if(len==1) {f[i][j]=0;continue;}for(int k=i;k

import java.util.*;class Main
{static int N=330;static int[][] f=new int[N][N];static int[] s=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();for(int i=1;i<=n;i++){s[i]=sc.nextInt();s[i]+=s[i-1];}for(int i=1;i<=n;i++)  Arrays.fill(f[i],0x3f3f3f3f);for(int len=1;len<=n;len++){for(int i=1;i+len-1<=n;i++){int j=i+len-1;if(len==1) {f[i][j]=0;continue;}for(int k=i;k

import java.util.*;class Main
{static int N=210;static long[][] f=new long[N][N]; //f[i][j]:把头标记i 尾标记j这段能量珠合成一段的最大能量static int[] w=new int[N]; //为能量珠的能量public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();for(int i=1;i<=n;i++){w[i]=sc.nextInt();w[n+i]=w[i]; //解决环形问题}for(int len=3;len<=2*n;len++) //i和j间至少有一个中间值才能合成{for(int i=1;i+len-1<=n*2;i++){int j=i+len-1;//k为合并两珠子的中间值(前一个的尾，后一个的头) for(int k=i+1;k