UVA 10003 Cutting Sticks 区间DP-白红宇

UVA 10003 Cutting Sticks 区间DP

阅读量：6148 次

发布时间：2019-06-21

本文共 1563 字，大约阅读时间需要 5 分钟。

　　题目链接： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944

　　题目大意：给你一个长度为L的木条，和N个切割点，每次切割的代价是当前切割木条的长度，问最小代价是多少。

　　解题思路：很显然的区间DP， dp(i, j)表示在i号和j号点之间切割的最小代价。dp转移方程为dp(i, j) = min(dp(i, k)+dp(k,j)+a[j]-a[i])|k属于(i, j)　　

　　代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 using namespace std;const int INF = 0x3fffffff;int dp[100][100]; // d(i, j)在 [i , j] 区间切割的最优费用int n;int a[100];int main() { int l; while( ~scanf( "%d", &l ) && l ) { scanf( "%d", &n ); a[0] = 0; a[n+1] = l; for( int i = 1; i <= n; i++ ) { scanf( "%d", &a[i] ); } for( int i = 0; i <= n+1; i++ ) { for( int j = 0; j <= n+1; j++ ) { dp[i][j] = INF; } } for( int i = 0; i <= n; i++ ) { dp[i][i+1] = 0; } for( int d = 2; d <= n+1; d++ ) { for( int s = 0; s <= n+1; s++ ) { for( int k = s+1; k < s+d; k++ ) { dp[s][s+d] = min( dp[s][s+d], dp[s][k] + dp[k][s+d] + a[s+d] - a[s] ); } } }// for( int i = 0; i <= n+1; i++ ) {// for( int j = 0; j <= n+1; j++ ) {// cout << dp[i][j] << " ";// }// cout << endl;// } printf( "The minimum cutting is %d.\n", dp[0][n+1] ); } return 0;}

View Code

　　思考：这道题本身没有多难，但是要注意的地方有很多，比如说一定要注意转移的方向，在算转移方程的左侧的时候一定要保证方程的右侧已经算了出来，就比如说这道题，想要计算区间（i, j）就必须保证我这个区间内所有只需要切割一下的，就是说中间隔了一个点的要全部都算出来，然后才能算隔两个点的，隔三个点的.......否则，如果像我一开始想的先枚举两个端点，再枚举中间点，就只能那函数做了，但是我们现在锻炼的是动态规划的思维......

转载于:https://www.cnblogs.com/FriskyPuppy/p/7281380.html

你可能感兴趣的文章