又双叕是洛谷原题。这也是一道动规题因为标签是动规

重点:

• dp数组含义:dp[i][j]为以a[i]开头a[j]结尾的串释放出的最大总能量。
• 状态转移方程为:dp[i][j]=max(dp[i][j],dp[j][k]+dp[k][j]+a[i]*a[k]*a[j])。
• 注意边界!这是一个环吧。所以要枚举起点
• 遍历顺序:双重,一个枚举长度,一个枚举起点。
• 然后就没有然后了...

代码:

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int dp[401][401];
int n,a[205]; 

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        a[n + i] = a[i];//因为这是一个环qwq
    } 
    for(int i = 2;i <= n + 1;i++) //长度 
    {
        for(int j = 1;j + i - 1 <= 2 * n;j++) //起点 
        {
            int endx = j + i - 1; //终点 
            for(int k = j + 1;k <= j + i - 2;k++) //分界线 
            {
            	dp[j][endx] = max(dp[j][endx],dp[j][k] + dp[k][endx] + a[j] * a[k] * a[endx]);
			}
        }
    }
    int maxn = -1e9;
    for (int i = 1;i <= n;i++) 
	{
		maxn = max(maxn,dp[i][n + i]);
	}
    cout << maxn;
    return 0;
}

环形区间合并模板题,还是比较水的

#include <iostream>
using namespace std;
const int N=1e3+10;
struct node{
	int bg;
	int ed;
}a[N];
int b[N],dp[N][N];
int main(){
	int n;cin>>n; 
	for(int i=1;i<=n;i++){
		cin>>b[i];
		b[i+n]=b[i];
	}
	for(int i=1;i<2*n;i++){
		a[i].bg=b[i],a[i].ed=b[i+1];
	}
	a[2*n].bg=b[2*n],a[2*n].ed=b[1];
	for(int i=2*n-1;i>=1;i--){
		for(int j=i+1;j<=2*n&&j-i+1<=n;j++){
			for(int k=i;k<j;k++){
				dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i].bg*a[k].ed*a[j].ed);
			}
		}
	}
	int mx=0;
	for(int i=1;i<=n;i++){
		mx=max(mx,dp[i][i+n-1]);
	}
	cout<<mx<<endl;
	return 0;
}