矩阵连乘核心代码
1 for(int i=0;i<=n;i++) 2     m[i][j]=0; 3 for(r=1;r<n;r++) 4     for(i=1;i<=n-r;i++) 5     { 6         j=i+r; 7         m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; 8         s[i][j]=i; 9         for(k=i+1;k<j;k++)10         {11             int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];12             if(t<m[i][j])13             {14                 m[i][j]=t;15                 s[i][j]=k;16             }17         }18     }

  1 /*  2     Name:   3     Copyright:   4     Author:   5     Date: 13/08/14 22:32  6     Description:   7     矩阵连乘  8     A1*A2*……An  9     m[i][j]表示AI到AJ这个整体的矩阵的最大值  m[i][i]=0; 10     设他们在K处断开。 11     则有m[i][j]=m[i][k]+m[k+1][j]+p(i-1)*pi*pj;i<=k<j;  12     现在给出一个表达式，运算符号只有+  *，运算对象为整数。 13     加括号求最大值     14 */ 15 #include"iostream" 16 #include"cstring" 17 #include"algorithm" 18 #include"cstdio" 19 using namespace std; 20 #define SUM 101 21 #define MAX 0x7fffffff 22 #define MIN -0x7fffffff 23 int n,num[SUM],ope[SUM],a[4]; 24 struct rem{ 25     int max; 26     int min; 27 };  28 rem result[SUM][SUM]; 29 rem cmp(int a1,int a2,int b1,int b2) 30 { 31     int i=0; 32     int max=MIN,min=MAX,tmp;  33     if((tmp=a1*b1)>max) 34         max=tmp; 35     if(tmp<min) 36         min=tmp; 37     if((tmp=a1*b2)>max) 38         max=tmp; 39     if(tmp<min) 40         min=tmp; 41     if((tmp=a2*b1)>max) 42         max=tmp; 43     if(tmp<min) 44         min=tmp; 45     if((tmp=a2*b2)>max) 46         max=tmp; 47     if(tmp<min) 48         min=tmp; 49     rem p; 50     p.max=max; 51     p.min=min; 52     return p; 53 } 54 rem maxv(int i,int j) 55 { 56     if(i==j) 57     { 58         result[i][j].max=num[i]; 59         result[i][j].min=num[i]; 60         return result[i][j]; 61     } 62     if(i<j) 63     { 64         if(result[i][j].max!=MIN) 65             return result[i][j]; 66         else 67         { 68             for(int t=i;t<j;t++) 69             { 70                 rem tmpa=maxv(i,t); 71                 rem tmpb=maxv(t+1,j); 72                 if(ope[t]==1) 73                 { 74                     rem c=cmp(tmpa.max,tmpa.min,tmpb.max,tmpb.min); 75                     if(c.max>result[i][j].max) 76                         result[i][j].max=c.max; 77                     if(c.min<result[i][j].min) 78                         result[i][j].min=c.min; 79                 } 80                 else 81                 { 82                     int mm=tmpa.max+tmpa.max; 83                     if(mm>result[i][j].max) 84                         result[i][j].max=mm; 85                     int mi=tmpa.min+tmpb.min; 86                     if(mi<result[i][j].min) 87                         result[i][j].min=mi; 88                 } 89             } 90             return result[i][j]; 91         } 92     } 93 } 94 int main() 95 { 96     char ch; 97     while(scanf("%d",&n)!=EOF) 98     { 99         for(int i=1;i<n;i++)100         {101             scanf("%d",&num[i]);102             getchar();103             scanf("%c",&ch);104             if(ch==‘*‘)105                 ope[i]=1;106             else107                 ope[i]=0;108         }109         scanf("%d",&num[n]);110         for(int i=0;i<=n;i++)111             for(int j=0;j<=n;j++)112             {113                 result[i][j].max=MIN;114                 result[i][j].min=MAX;115             }116         int max=maxv(1,n).max;117         printf("%d\n",max);118     }119     return 0;120 }