一.能量项链

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

不用担心:题目说了:第一行是一个正整数N(4≤N≤100)N(4N100),表示项链上珠子的个数。

所以这么做可以ac。

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

01-06 05:34