rqnoj/5.2.c

   1 /*
   2 Way: DP
   3 Accept 485ms
   4 */
   5
   6 #include <stdio.h>
   7
   8 #define maxn 220
   9 #define max(p,q) ((p)>(q)?(p):(q))
  10
  11 int main() {
  12         int n;
  13         scanf("%d",&n);
  14         int i,a[maxn];
  15         for (i=1; i<=n; i++) {
  16                 scanf("%d",&(a[i]));
  17                 a[n+i]=a[i];
  18         }
  19         int f[maxn][maxn],k,len;
  20         for (len=2; len<=n; len++)
  21                 for (i=1; i<=n*2-len+1; i++)
  22                         for (k=i+1; k<=i+len-1; k++)
  23                                 f[i][i+len]=max(f[i][i+len],f[i][k]+f[k][i+len]+a[i]*a[k]*a[i+len]);
  24         int ans=0;
  25         for (i=1; i<=n; i++) ans=max(ans,f[i][i+n]);
  26         printf("%d\n",ans);
  27         return 0;
  28 }