这个题是一个十分经典的区间dp，也是最基础的区间dp
大体思路就是将大区间化为小区间去做，再通过小区间dp回来求大区间
首先，我们发现尽管题目中有着许多的关于吸盘的描述，实际上都是在搞心态
精简一下题目，就是给你一个环形的序列，让你求a[l]*a[k]*a[r]在每个区间合并时的取值的最大价值，与合并石子有类似的地方，但是本题的价值取数和之前合并石子的价值取数有所不同，在取值时是三个数的乘积相加（也就是题目中所说的那个通过吸盘来吸取其中的能量，即能量珠子的头标记，尾标记和自身的乘积，也就是我们的价值取数）
我们在设置dp数组时也去选择最简洁的dp[l][r]来表示在序列区间[l,r]上的最大价值，显然，我们只需要去枚举断点来进行dp就可以了
dp方程也不难理解：dp[l][r]=max(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[k]*a[r])
这里需要注意的点就是这个，枚举的时候应该先去枚举那个dp区间的长度i
只有先去确定好我们所要枚举的区间长度才能去进行之后的操作
这里还需要注意的地方就是那个环了，我们既可以通过%操作去实现环形也可以通过2*n数组去进行模拟这个环
我选择了后者，因为代码难度相对较小
代码如下：
#include<bits/stdc++.h> using namespace std; inline int read() { int a=0,b=1; char c=getchar(); while(!isdigit(c)) { if(c==‘-‘) b=-1; c=getchar(); } while(isdigit(c)) { a=(a<<1)+(a<<3)+(c^48); c=getchar(); } return a*b; } int a[205],dp[205][205]; int main() { int n=read(); for(int i=1;i<=n;i++) { a[i]=read(); a[i+n]=a[i]; } for(int i=2;i<=n+1;i++) for(int l=1;l+i-1<=2*n;l++) { int r=l+i-1; for(int k=l+1;k<=l+i-2;k++) dp[l][r]=max(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]); } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,dp[i][i+n]); printf("%d",ans); return 0; }
原文：https://www.cnblogs.com/gongcheng456/p/12995107.html