# 題目: 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