# 題目: UVa 10003 - Cutting Sticks

# 題目說明

你需要將一條木頭特定的點切割，每次 cost 木頭當前的長度，求最小的切割 cost

例如:
長 100 公分的木頭，你需要在 25、50、75 的地方切割
1.
若你按 25、50、75 的順序切割
第一次 cost 100 ，木頭剩下 75 公分 (25 ~ 100)
第二次 cost 75 ，木頭剩下 50 公分 (50 ~ 100)
第二次 cost 50 ，木頭剩下 25 公分 (75 ~ 100)
這樣的總 cost = 225
2.
若你按 50、25、75 或 50、72、25 的順序切割
總 cost 會是 100 + 50 + 50 = 200

INPUT:
每筆測資第一行輸入一個整數 L ，代表木頭的長度
第二行輸入一個整數 N ，代表切割的次數
接著會有 N 個整數，代表切割的位置

當 L 為 0 時結束程式

OUTPUT:
輸出最小的切割 cost

# 解題方法

先將切割點存入 wood ，從 1 ~ N
wood[0] 放 0， wood[N + 1] 放 L
所以我們會得到一個表 wood[] = {0, 25, 50, 75, 100}

接下來就是動態規劃的部份
當 r = 1 也就是只有一塊的時候，不需要切割，所以 cost 為 0 ，所以我們的程式直接從 r = 2 開始
先從小塊的切割開始，慢慢往後處理
按照例子會跑以下:

1. r=2 b=0 e=2 : dp[0][2] = 50
2. r=2 b=1 e=3 : dp[1][3] = 50
3. r=2 b=2 e=4 : dp[2][4] = 50
4. r=3 b=0 e=3 : dp[0][3] = 125
5. r=3 b=1 e=4 : dp[1][4] = 125
6. r=4 b=0 e=4 : dp[0][4] = 200

# 參考程式碼

#include <iostream>

#include <memory.h>

#include <climits>

using namespace std;

int dp[52][52];

int wood[52];

int main()

{

	// fast io

	ios::sync_with_stdio(false);

	cin.tie(nullptr);

	cout.tie(nullptr);

	int L, N, a, e;

	while (cin >> L, L && cin >> N)

	{

		memset(wood, 0, sizeof(wood));

		memset(dp, 0, sizeof(dp));

		// wood[0] is 0, wood[N + 1] is L

		for (int i = 1; i <= N; ++i) cin >> wood[i];

		wood[++N] = L;

		// when r = 0, the cost is always 0, so we start with r = 2

		for (int r = 2; r <= N; ++r) for (int b = 0; b < N; ++b)

		{

			if ((e = b + r) > N) break;

			dp[b][e] = INT_MAX;

			for (int c = b + 1; c < e; ++c)

			{

				int tmp = dp[b][c] + dp[c][e] + wood[e] - wood[b];

				dp[b][e] = min(dp[b][e], tmp);

			}

		}

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

	}

	return 0;

}

# 參考資料

http://worldofmonmon.blogspot.com/2018/02/uva-10003-cutting-sticks-dp.html