网站建议:179001057@qq.com

矩阵连乘

技术2022-05-12  0

#include <iostream>#include <cstring>#include <cstdio>#define MAX 1000

using namespace std;

int m[MAX][MAX];int s[MAX][MAX];//fenge qingkuangint count = 0;

void MatrixChain(int p[],int n,int m[][MAX],int s[][MAX]){    for(int i = 1;i <= n;i++) m[i][i] = 0;

    for(int r = 2;r <= n;r++)      for(int i = 1;i <= n - r + 1;i++){          int j = i + r - 1;          m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];          s[i][j] = i;          for(int k = i+1;k < j;k++){              int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];              if(t < m[i][j]){                  m[i][j] = t;                  s[i][j] = k;              }          }      }}

void Traceback(int i,int j,int s[][MAX])//输出{    if(i == j ) cout<<"A"<<i;    else{        cout<<"(";        Traceback(i,s[i][j],s);        cout<<" x ";        Traceback(s[i][j]+1,j,s);        cout<<")";    }}int main(){   // freopen("in.in","r",stdin);    int n;    int p[MAX];//维数    int count = 0;    while(cin>>n && n){        count++;        cout<<"Case "<<count<<": ";        int temp,i;        //输入维数        for( i = 0;i < n-1;i++)            cin>>p[i]>>temp;        cin>>p[i];i++;        cin>>p[i];

        MatrixChain(p,n,m,s);//DP求解

        Traceback(1,n,s);

        cout<<endl;    }    return 0;}


最新回复(0)