能量项链---动态规划（C语言）

解题思路:

参考此视频，讲的很详细    能量项链 区间DP

看完视频根据代码注释应该理解起来问题不大

参考代码:

#include<stdio.h>
#define MAX 101
#define max(a,b) a>b?a:b

int main(){
	int n,result_max=0; 
	int a[MAX],i,r,len,k;// i表示起始位置，len表示区间长度，r表示区间终点 
	int dp[MAX][MAX]={0};
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i+n]=a[i];  //断环为链，即复制一遍数据加在后面 
	}
	for(len=3;len<=n+1;len++)//确定区间长度
	{
		for(i=1;i+len-1<=2*n;i++)//确定左右区间[i,r]范围
		{
			r=i+len-1;		//确定区间终点 
			for(k=i+1;k<r;k++)//确定区间分段点位置
			{
				dp[i][r]=max(dp[i][r],dp[i][k]+dp[k][r]+a[i]*a[k]*a[r]);//此公式根据视频理解 
			}
			if(dp[i][r]>result_max) result_max=dp[i][r];
			// 比较每个区间大小，找出最大值(其实最大值只会在区间长度n+1的区间里，在这里逐一比较只是为了代码简单) 
		}
	}
	printf("%d",result_max);
}