rqnoj/49.c

   1 #include <stdio.h>
   2
   3 #define maxn 35
   4
   5 int score[maxn],opt[maxn][maxn],root[maxn][maxn];
   6
   7 int max(int p, int q)
   8 {
   9         return p>q?p:q;
  10 }
  11
  12 int mdfs(int l, int r)
  13 {
  14         int i;
  15         if (opt[l][r]) return opt[l][r];
  16         if (l==r) return score[l];
  17         if (l>r) return 1;
  18         int tmp=0;
  19         for (i=l; i<=r; i++)
  20         {
  21                 opt[l][i-1]=mdfs(l,i-1);
  22                 opt[i+1][r]=mdfs(i+1,r);
  23                 tmp=opt[l][i-1]*opt[i+1][r]+score[i];
  24                 if (tmp>opt[l][r])
  25                 {
  26                         opt[l][r]=tmp;
  27                         root[l][r]=i;
  28                 }
  29         }
  30         return opt[l][r];
  31 }
  32
  33 void printroot(int l, int r)
  34 {
  35         if (l>r) return;
  36         printf("%d ",root[l][r]);
  37         printroot(l,root[l][r]-1);
  38         printroot(root[l][r]+1,r);
  39 }
  40
  41 int main()
  42 {
  43         int n,i,j;
  44         scanf("%d",&n);
  45         for (i=1; i<=n; i++)
  46         {
  47                 scanf("%d",&(score[i]));
  48                 opt[i][i]=score[i];
  49                 root[i][i]=i;
  50         }
  51         printf("%d\n",mdfs(1,n));
  52         printroot(1,n);
  53         printf("\n");
  54         return 0;
  55 }