【能量项链】 （C++代码）

解题思路:





注意事项:





参考代码:

//区间动规 //重点就是将整体划分为区间，小区间之间合并获得大区间//状态转移方程的推导如下//一、将珠子划分为两个珠子一个区间时，这个区间的能量=左边珠子*右边珠子*右边珠子的下一个珠子//二、区间包含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;
}

评论

Rye_Catcher
讲的真的好

ACnanyang
谢谢

评论

作者: NewErA 更新时间: 2017-09-02 16:14  在Ta的博客查看  4 

第一次遇到区间dp，写个题解总结一下

区间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;
}

评论

还没有评论

评论

作者: yangkai 更新时间: 2017-10-07 13:42  在Ta的博客查看  2 

题目略水，注意边界即可

注意边界！

思考的时候注意这是一个环，嗯所以以每一个点为起点进行一次DP，记忆花搜索时间是没有问题的。然后其次就是递推。

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

代码君

'''cpp

#include<bits/stdc++.h>using namespace std;#define N 310int f[N][N];int a[N];int n;int dp(int l,int r){    int &ans=f[l][r];    if(ans)return ans;    if(l==r-1)return ans=a[l]*a[r]*a[r+1];    for(int i=l;i<r;i++)
       ans=max(ans,a[l]*a[i+1]*a[r+1]+dp(l,i)+dp(i+1,r));    return ans;
}int main(){    cin>>n;    for(int i=1;i<=n;i++)cin>>a[i],a[n+i]=a[i];
   a[2*n+1]=a[1];    int ans=0;    for(int i=1;i<=n;i++)
       ans=max(ans,dp(i,i+n-1));    cout<<ans;    return 0;
}

'''

评论

还没有评论

评论

作者: 非凡 更新时间: 2017-11-10 10:18  在Ta的博客查看  1 

//f[i,j]表示从第i颗珠子合并到第j个珠子的最大得分

//由于这是一个圈，所以考虑把它拉直成一条链。

//但是会循环啊，怎么办？

//所以拉直的时候将整条复制到后面

//时间O(8*n^2), 注意开long long(我很久以前打的P，懒得写C++了)

代码：

var n,i,j,k:longint;
   max:int64;
   a:array[-10..maxint] of int64;
   f:array[1..1000,1..1000] of int64;begin
 readln(n);  for i:=1 to n do
 begin
   read(a[i]);
   a[n+i]:=a[i];//拉直成2*n长
 end;  for i:=2*n-1 downto 1 do
 for j:=i+1 to 2*n do
 for k:=i to j-1 do
 if f[i,k]+f[k+1,j]+a[i]*a[k+1]*a[j+1]>f[i,j]
 then begin
        f[i,j]:=f[i,k]+f[k+1,j]+a[i]*a[k+1]*a[j+1];         if f[i,j]>max then max:=f[i,j];       end;
 writeln(max div 2);end.

评论

还没有评论

评论

作者: ex_jason 更新时间: 2017-11-07 12:53  在Ta的博客查看  1 

设d[i]表示第i颗珠子头标记,则d[i+1]为尾标记 ;

• 设f[i,j]表示从第i颗珠子一直合并到第j堆颗珠子所

产生的最大能量,如果这个任务最后一次合并在

第k位置,则状态转移方程为

• f[i,j]=max{f[i,k]+ f[k+1,j]+d[i]*d[k+1]*d[j+1]]} , k= i~

j-1 • 边界条件:f[i,i]=0

• 以长度从小到大划分阶段

• 时间复杂度O(n^3 )

AC代码：

#include<iostream>using namespace std;int n,e[250],f[250][250]={0};int main(){    int i,j,k,mx=0;    cin>>n;    for (i=1;i<=n;i++)
   {        cin>>e[i];
       e[n+i]=e[i];//形成一个环
   }    for (j=2;j<=2*n-1;j++)//起点
           for (i=j-1;i>0&&j-i<n;i--)//终点
                   for (k=i;k<j;k++)//选合并的点
                           f[i][j]=max(f[i][k]+f[k+1][j]+e[i]*e[k+1]*e[j+1],f[i][j]);//状态转移方程
   for (i=1;i<=n;i++)
           mx=max(mx,f[i][i+n-1]);    cout<<mx<<endl;    return 0;
}