p1056题解

1.介绍一种实用的简单的方法：

//区间动规 //重点就是将整体划分为区间，

小区间之间合并获得大区间//状态转移方程的推导如下

//一、将珠子划分为两个珠子一个区间时，这个区间的能量=左边珠子*右边珠子*右边珠子的下一个珠子

//二、区间包含3个珠子，可以是左边单个珠子的区间+右边两珠子的区间，

或者左边两珠子的区间右边+单个珠子的区间 

//即，先合并两个珠子的区间，

释放能量，加上单个珠子区间的能量（单个珠子没有能量。。）

//Energy=max(两个珠子的区间的能量+单个珠子区间的能量，

单个珠子的区间的能量+两个珠子的区间的能量 ）

 //三、继续推4个珠子的区间，5个珠子的区间。

 //于是可以得到方程：Energy=max（不操作的能量，

 左区间合并后的能量+右区间合并后的能量+两区间合并产生能量）

 //两区间合并后产生的能量=左区间第一个珠子*右区间第一个珠子*总区间后面的一个珠子 

 #include<bits/stdc++.h>

 using namespace std;

 int n,e[300],s[300][300],maxn=-1;

 int main(){ 

 cin>>n;

 for(int i=1;i<=n;i++)

 {cin>>e[i];e[i+n]=e[i];} 

    //珠子由环拆分为链，重复存储一遍

    for(int i=2;i<2*n;i++){      

      for(int j=i-1;i-j<n&&j>=1;j--){//从i开始向前推

            for(int k=j;k<i;k++)//k是项链的左右区间的划分点

             s[j][i]=max(s[j][i],s[j][k]+s[k+1][i]+e[j]*e[k+1]*e[i+1]);

                         //状态转移方程：max(原来能量，左区间能量+右区间能量+合并后生成能量） 

            if(s[j][i]>maxn)maxn=s[j][i];//求最大值

        }

    }

    cout<<maxn; 

       return 0;

  }

  2.不推荐，但也可以用：

 区间dp能解决的问题就是通过小区间更新大区间，最后得出指定区间的最优解

个人认为，想要用区间dp解决问题，首先要确定一个大问题能够剖分成几个相同较小问题，且小问题很容易组合成大问题，从而从解决小问题逐渐解决大问题，体现的其实是分治的思想，只不过是通过dp用递推的方式解决了。比如floyd现在看来也属于区间dp 的一种。

本题应通过演算过程发现最终问题的解决可由两个相同规模较小的问题轻松地转化过来。（一般分治时只分成两个简化程序） 用f[l][r]表示以a[l]开头a[r]结尾的数串的最大和，如k为i,j之间任一节点，有f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]); 对l,r的定义自己一定要十分清晰，从而确定好循环的边界。

本题的小技巧：在环形问题中，可以选择(i+1)%n的方式，但也可以将n个元素复制一遍，变成2*n个元素，简化代码。

但也有问题随之而来，在更新时要将2*n个元素都更新，而不能只更新到前n个，否则访问到n+1~2n时会出错

附上代码：

#include <bits/stdc++.h>

using namespace std;

int f[405][405];int n,a[205];

int main(){ 

   cin >> n;

       for(int i=1;i<=n;i++)  

       //***对环形问题的处理技巧***

    {   

       cin >> a[i];

        a[n+i]=a[i];

    } 

    for(int i=2;i<=n+1;i++)

    {    

        for(int l=1;l+i-1<=2*n;l++)  //如果采取了上述策略，一定要将2*n个点都更新 

       {     

              int r=l+i-1;            for(int k=l+1;k<=l+i-2;k++)

                f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]); 

        }

    }   

     int res=0;  

       for (int i=1;i<=n;i++) res=max(res,f[i][n+i]);    

       cout << res; 

          return 0;

          }