本文主要是介绍uva 348 Optimal Array Multiplication Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给你n个矩阵，要你计算矩阵乘的最少运算量。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=12;
struct node
{int x,y;
}m[N];
int map[N][N],ileft[N],iright[N];
int dp(int,int);
void find_ans(int,int);
int main()
{int n,t_cnt=0;while(scanf("%d",&n)!=EOF){if(n==0) break;memset(map,0,sizeof(map));memset(ileft,0,sizeof(ileft));memset(iright,0,sizeof(iright));ileft[0]++;iright[n-1]++;for(int i=0;i<n;i++) scanf("%d%d",&m[i].x,&m[i].y);printf("Case %d: ",++t_cnt);int ans=dp(0,n-1);find_ans(0,n-1);for(int i=0;i<n;i++){if(i!=0) printf(" x ");while(ileft[i]--) printf("(");printf("A%d",i+1);while(iright[i]--) printf(")");}//printf("ans=%d\n",ans);puts("");}return 0;
}
int dp(int be,int end)
{if(map[be][end]!=0) return map[be][end];else if(end-be==1) {map[be][end]=m[be].x*m[end].y*m[end].x;return map[be][end];}else if(end==be) return 0;else{int imin=1<<30;for(int i=be;i<end;i++){imin=min(imin,dp(be,i)+dp(i+1,end)+m[be].x*m[end].y*m[i+1].x);}map[be][end]=imin;return imin;}
}
void find_ans(int be,int end)
{if(be==end||be+1==end) return;else{int imin=1<<30,pos;for(int i=be;i<end;i++){int temp=map[be][i]+map[i+1][end]+m[be].x*m[end].y*m[i+1].x;if(imin>temp){imin=temp;pos=i;}}if(pos!=be) {ileft[be]++;iright[pos]++;}if(pos+1!=end) {ileft[pos+1]++;iright[end]++;}find_ans(be,pos);find_ans(pos+1,end);}
}
这篇关于uva 348 Optimal Array Multiplication Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
