題目： UVa - 10003 - Cutting Sticks

題目說明

有一個可以切割木頭的工作台，若切割長度為 l 的木頭則需要消耗成本 l，且只能切割一個點，給一個木頭的長度及一些切割點，求將所有切割點都切割所需要的最小總成本。

Input： 每組測資第一個整數為 l，為要切割的木頭總長度，若為 0 表結束。後面一個整數 n，表有 n 個切割點，後面 n 個整數為切割點距離起始點的長度。

Output： 輸出將所有切割點都切割後的最小成本。

解題思路

我國文不太好，這題不知道怎麼用文字解釋，其實我也看不懂我在寫啥，建議直接看這篇比較快。

動態規劃題。

先讀取測資，使用 cut 數組儲存所有切割點，並將 l 放在最後面，0 放在最前面，為了方便，先在這裡將 n + 1。

定義 dp[i][j] 表切割 切割點 i ( cut[i] ) 及 切割點 j ( cut[j] ) 中所有切割點的最小花費。

核心概念為，先從最小塊的木頭開始切割，找出最小塊的木頭需要消耗的成本，以此來算出大塊的木頭需要消耗的成本，將程式碼具體化來說，以 Sample I/O 的第一組測資舉例：

1
2
3
4
100
3
25 50 75
cut[] = { 0, 25, 50, 75, 100 }

一開始木頭的長度為 100，成本為 100，若第一刀在 50 的地方切割，則

  • 總成本 = ( 0 ~ 50 的木頭完全切割需要的最小成本 ) + ( 50 ~ 100 的木頭完全切割需要的最小成本 ) + ( 100 - 0 )
    dp[0][4] = dp[0][2] + dp[2][4] + ( cut[4] - cut[0] )

  • 0 ~ 50 的木頭完全切割需要的最小成本 = ( 0 ~ 25 的木頭完全切割需要的最小成本 ) + ( 25 ~ 50 的木頭完全切割需要的最小成本 ) + ( 50 - 0 )
    dp[0][2] = dp[0][1] + dp[1][2] + ( cut[2] - cut[0] )

  • 50 ~ 100 的木頭完全切割需要的最小成本 = ( 0 ~ 25 的木頭完全切割需要的最小成本 ) + ( 25 ~ 50 的木頭完全切割需要的最小成本 ) + ( 100 - 50 )
    dp[2][4] = dp[2][3] + dp[3][4] + ( cut[4] - cut[2] )

  • 0 ~ 25 的木頭完全切割需要的最小成本 = 0

  • 25 ~ 50 的木頭完全切割需要的最小成本 = 0

雖然想法是從上往下，但實際計算的時候需要從下往上計算，簡單來說，就是從小塊的木頭開始枚舉需要的成本，之後推到大塊的木頭，剩下的就看程式碼吧。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/fZFwfx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

const int inf = (int)1e9;

int l, n;
int dp[52][52]; // dp[i][j] 表切割 i 及 j 中所有切割點的最小花費
int cut[52];    // 木頭切割點

void read()
{
    cin >> n;
    cut[++n] = l;
    for (int i = 1; i < n; ++i) cin >> cut[i];
}

void solve()
{
    // args:
    // w -> wide  枚舉的區間寬度
    // l -> left  左端點
    // r -> right 右端點
    // m -> mid   中間
    for (int w = 2; w <= n; ++w) for (int l = 0; l < n - 1; ++l)
    {
        int r = l + w;
        if (r > n) break;
        dp[l][r] = INT_MAX;
        for (int m = l + 1; m < r; ++m)
            dp[l][r] = min(dp[l][m] + dp[m][r] + cut[r] - cut[l], dp[l][r]);
    }
    cout << "The minimum cutting is " << dp[0][n] << ".\n";
}

int main()
{
    while (cin >> l && l)
    {
        read();
        solve();
    }
}

參考資料

萌萌萌萌的筆記: UVA 10003 Cutting Sticks (DP)