区间dp体会

一.能量项链

https://www.luogu.org/problem/P1063

（这道题和紫书里的最优矩阵链乘很像）

①分析样例：

4
2 3 5 10

我们把它写成4个乘法表达式：

2*3 3*5 5*10 10*2

合并它需要3次乘法：

10*2*3 3*5 5*10 能量+60

10*2*3*5 5*10 能量+10*3*5

10*2*3*5*10 能量+10*5*10

总能量就是710

其实表达式还可以这么写

2*3*5*10*2*3*5*10，然后我们要做的就是加括号（回到了最优矩阵链乘），

每次算出来的值都加起来，

2*10*3

+10*3*5

+10*5*10

我们设f[ i ][ j ]为从i乘到j得到的最大能量

边界：f[ i ][ i ]=0，f[ i ][ i+2 ]=data[ i ]*data[ i+1]*data[ i+2 ];

f[ i ][ j ]=max(f[ i ][ k ]+f[ k ][ j ]+data[ i ]*data[ k ]*data[ j ]);

状态转移：

for(int l=3;l<=n;l++)
       for(int i=1,j=i+l;j<=n*2;i++,j++) //不要把终止条件打成i<=n了，那样会有一些小区间扫不出来 
         for(int k=i+1;k<j;k++) 
         {
             f[i][j]=max((f[i][k]+f[k][j])+d[i]*d[k]*d[j],f[i][j]);
         }

最后在f[ 1 ][ 1+n ]到f[ n ][ n+n ]里把ans找出来

（至于为什么是+n，楼主觉得是因为要进行n-1次运算，如果你有更好的解释，请留言

是不是觉得有问题，如果数据是这样的呢

2 3

不用担心：题目说了：第一行是一个正整数

所以这么做可以ac。

二.待更新，楼主要去做别的题了