UVA 10003 Cutting Sticks

题目链接~~>

做题感悟：这题属于区间DP，开始做事看着和矩阵连乘一样，结果没想出状态转移方程。

解题思路：给木棍添加 一个头一个尾就成为矩阵连乘问题了，从小递推到达最终结果就为dp[ 0 ][ L ] .

     状态方程：dp[ i ][ j ] = min { dp [ i ] [ k ] +dp[ k ] [ j ] +d[ j ]  - d[ i ]  } dp[ i ][ j ] 代表从第 i 处到第 j 处的最优解。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int MX = 50 + 10 ;
     
    
   

    

     

    
    

     

      int L,n ;
     
    
   

    

     

    
    

     

      int dp[MX][MX],a[MX] ;
     
    
   

    

     

    
    

     

      void SectionDP()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i=0 ;i<=n ;i++)
     
    
   

    

     

    
    

     

       dp[i][i+1]=0 ;
     
    
   

    

     

    
    

     
 for(int t=2 ;t<=n ;t++)
     
    
   

    

     

    
    

     
 for(int i=0 ;i+t<=n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dp[i][i+t]=INF ;
     
    
   

    

     

    
    

     
 for(int j=i+1 ;j<i+t ;j++)
     
    
   

    

     

    
    

     

       dp[i][i+t]=min(dp[i][i+t],dp[i][j]+dp[j][i+t]+a[i+t]-a[i]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<"The minimum cutting is "<<dp[0][n]<<"."<<endl ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(scanf("%d",&L),L)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d",&n) ;
     
    
   

    

     

    
    

     

       a[0]=0 ; // 添加尾
     
    
   

    

     

    
    

     
 for(int i=1 ;i<=n ;i++)
     
    
   

    

     

    
    

     
 scanf("%d",&a[i]) ;
     
    
   

    

     

    
    

     

       a[++n]=L ;// 添加头
     
    
   

    

     

    
    

     

       SectionDP() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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