沧海一声喵 2018-02-08 02:30:11
点我顶贴
收藏
删除
#include <cstdio>
#include <cstring>
using namespace std;
typedef struct node{
int qian,hou;
}node;
int main(){
int p,max=0,i,j,k,n,x,dp[201][201];node w[201];
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&x);
w[i-1].hou=w[i].qian=x;}
w[n].hou=w[1].qian;
for(i=1;i<=n;i++) w[i+n]=w[i];
for(p=1;p<=n;p++){
memset(dp,0,sizeof(dp));
for(i=p+n-2;i>=p;i--)
for(j=i+1;j<=p+n-1;j++)
for(k=i;k<j;k++)
if(dp[i][k]+dp[k+1][j]+w[i].qian*w[k].hou*w[j].hou>dp[i][j])
dp[i][j]=dp[i][k]+dp[k+1][j]+w[i].qian*w[k].hou*w[j].hou;
if(dp[p][p+n-1]>max) max=dp[p][p+n-1];}
printf("%d",max);
return 0;}