做题感悟:这题上来一看就是矩阵连成,就是输出的时候有点不好输出。
解题思路:矩阵连乘:状态方程 -> dp[ i ][ j ] = min{ dp[ i ][ k ] +dp[ k+1 ][ j ] + p[ i ] * p[ k ]*p[ j ] }
代码:
#include<stdio.h> #include<vector> #include<queue> #include<string.h> #include<stdlib.h> #include<string.h> #include<algorithm> #include<iostream> #define INT __int64 const int INF = 99999999 ; using namespace std ; const int MX = 100 + 10 ; int n ; int m[MX][MX],s[MX][MX],p[MX] ; void Matrix() { for(int i=1 ;i<=n ;i++) { m[i][i]=0 ; s[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 temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j] ; if(temp<m[i][j]) { m[i][j]=temp ; s[i][j]=k ; } } } } void print(int i,int j) { if(i==j) { cout<<"A"<<i ; return ; } cout<<"(" ; print(i,s[i][j]) ; cout<<" x " ; print(s[i][j]+1,j) ; cout<<")" ; } int main() { int x,cse=1 ; while(scanf("%d",&n),n) { scanf("%d",&p[0]) ; for(int i=1 ;i<=n ;i++) { scanf("%d",&p[i]) ; if(i!=n) scanf("%d",&x) ; } Matrix() ; cout<<"Case "<<cse++<<": " ; print(1,n) ; cout<<endl ; } return 0 ; }