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

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=205;
int a[M][M];
int b[M];
int main()
{
	int n,sum=0;
	cin>>n;
	memset(a,0,sizeof(a));
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
		b[i+n]=b[i];
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j+i-1<2*n;j++)
		{  
			int t=j+i-1;
		    for(int k=j;k<t;k++)
			{
				a[j][t]=max(a[j][t],a[j][k]+a[k+1][t]+b[j]*b[k+1]*b[t+1]);
			}  
	    }
	}
	for(int i=1;i<=n;i++)
	{
	 	if(sum<a[i][i+n-1])
	 	sum=a[i][i+n-1];
	}
	cout<<sum<<endl;
	return 0;
}