UVA 348 Optimal Array Multiplication Sequence (区间DP)

题目链接~~>

做题感悟：这题上来一看就是矩阵连成，就是输出的时候有点不好输出。

解题思路：矩阵连乘：状态方程 ->   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 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/37873173