1 #include <iostream>

 2

 3 using namespace std;

 4

 5 const int MAXN=110;

 6

 7 int n;

 8 int a[MAXN*2];

 9 int dp[MAXN*2][MAXN*2];

10

11 int main()

12 {

13     cin>>n;

14     for (int i=1;i<=n;i++)

15     {

16         cin>>a[i];

17         a[i+n]=a[i];

18     }

19

20     for (int len=2;len<=n;len++)   //枚举合并长度

21     {

22         for (int i=1;i+len-1<=2*n;i++)   //枚举左端点

23         {

24             int j=i+len-1;   //右端点

25             for (int k=i;k<=j-1;k++)   //枚举间断点

26             {

27                 dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]);

28             }

29         }

30     }

31

32     int ans=0;

33     for (int i=1;i<=n;i++)

34     {

35         ans=max(ans,dp[i][i+n-1]);

36     }

37     cout<<ans<<endl;

38

39     return 0;

40 }