~~~ #include <iostream> using namespace std; void show(int **s,int i,int j){ if(i==j) cout<<"A"<<i; else{ cout<<"("; show(s,i,s[i][j]); show(s,s[i][j]+1,j); cout<<")"; } } void answer(int *a,int n){ int **m = new int *[n]; for(int i=0;i<n;i++) m[i] = new int[n]; for(int i=0;i<n;i++) for(int j=0;j<n;j++) m[i][j] = -1; int **s = new int *[n]; for(int i=0;i<n;i++) s[i] = new int[n]; for(int i=0;i<n;i++) m[i][i] = a[i]; for(int l=1;l<n;l++){ for(int i=0;i<n-l;i++){ int j = i + l; m[i][j] = -1; for(int k=i;k<j;k++){ int p = (m[i][k] + m[k+1][j])*2; if(p>m[i][j]) { m[i][j] = p; s[i][j] = k; } } } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cout<<m[i][j]<<"\t"; cout<<endl; } show(s,0,n-1); for(int i=0;i<n;i++) delete s[i],m[i]; delete m,s; } ~~~