UVA 10003 Cutting Sticks 区间DP

红太狼 2021-03-30 15:53 415阅读 0赞

题目大意： 给你一个长度为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 <iostream>
    #include <cstdio>
    #include <string>
    #include <vector>
    #include <map>
    #include <cstring>
    #include <iterator>
    #include <cmath>
    #include <algorithm>
    #include <stack>
    #include <deque>
    #include <map>
    
    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）就必须保证我这个区间内所有只需要切割一下的， 就是说中间隔了一个点的要全部都算出来， 然后才能算隔两个点的， 隔三个点的.......否则，如果像我一开始想的先枚举两个端点， 再枚举中间点， 就只能那函数做了， 但是我们现在锻炼的是动态规划的思维......