rqnoj/5.1.c

   1 /*
   2 Way: memorized-DFS
   3 Accept  858ms
   4 */
   5
   6 #include <stdio.h>
   7
   8 #define maxn 220
   9
  10 int a[maxn],f[maxn][maxn];
  11
  12 int max(int p, int q) {
  13         return p>q?p:q;
  14 }
  15
  16 int query(int l, int r) {
  17         if (f[l][r]) return f[l][r];
  18         if (l>=r) return 0;
  19         int k;
  20         for (k=l+1; k<=r-1; k++) {
  21                 f[l][k]=query(l,k);
  22                 f[k][r]=query(k,r);
  23                 f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]);
  24         }
  25         return f[l][r];
  26 }
  27
  28 int main() {
  29         int n;
  30         int i;
  31         scanf("%d",&n);
  32         for (i=1; i<=n; i++) {
  33                 scanf("%d",&(a[i]));
  34                 a[n+i]=a[i];
  35         }
  36         int ans=0;
  37         for (i=1; i<=n; i++) ans=max(ans,query(i,i+n));
  38         printf("%d\n",ans);
  39         return 0;
  40 }