UVa 문제 10003 절단 스틱 (절단 나무 막대)

// Cutting Sticks （    ）
// PC/UVa IDs: 111105/10003, Popularity: B, Success rate: average Level: 2
// Verdict: Accepted
// Submission Date: 2011-10-14
// UVa Run Time: 0.548s
//
//     （C）2011，  。metaphysis # yeah dot net
//
// [    ]
//             ？
//
//              。               ，                 ，
//          A，B   ，    A，B        ，                ，  
//        。
//
//                          ？
//
//      ：             ，                    ，      
//         。
//
//      ，           ：        ，             ，      
//         ，            。
//
//      ，         ，         4，          6，       1，3，4
//    ，    3    ，        3    ，         ，  22，        
//      ？  ，  ，       ：
//
// 10
// 1 2 3 7
//
//              ，  1     7  。
//
//    ，       ，                          。
//
//         ？
//
//        ，          ，           A   B，   ，         
//     A   B               ，      A   B        ，       
//    。      minCost[i][j]     i          j                
//   ，      ，    k     ，            0     ，       k + 1
//     ，    i            places[i]，        ：
//
// minCost[i][j] = min{minCost[i][j], minCost[i][c] + minCost[c][j] + (places[j]
// - places[i])|i < c < j}
//
//    ，    i       i + 1          0，         ，     。   
//    ，        DP       ，             。

#include <iostream>

using namespace std;

#define min(a, b) ((a) <= (b) ? (a) : (b))

#define MAXCUTS 55
#define MAXCOST (1 << 20)

int length, cuts;
int places[MAXCUTS] = { 0 };
int minCost[MAXCUTS][MAXCUTS];

//    +     DP。
int cost(int start, int end)
{
	if (minCost[start][end] < MAXCOST)
		return minCost[start][end];
	
	for (int i = (start + 1); i <= (end - 1); i++)
	{
		int tmpCost = cost(start, i) + cost(i, end);
		tmpCost += (places[end] - places[start]);
		
		if (tmpCost < minCost[start][end])
			minCost[start][end] = tmpCost;
	}
	
	return minCost[start][end];
}

int main(int ac, char *av[])
{
	int money;

	while (cin >> length, length)
	{
		//              0   length。
		cin >> cuts;
		for (int i = 1; i <= cuts; i++)
			cin >> places[i];
		places[cuts + 1] = length;

		//         0    。
		money = 0;
		if (cuts)
		{
			for (int i = 0; i < MAXCUTS; i++)
				for (int j = 0; j < MAXCUTS; j++)
					minCost[i][j] = MAXCOST;
			for (int i = 0; i <= cuts; i++)
				minCost[i][i + 1] = 0;

			cost(0, cuts + 1);
			money = minCost[0][cuts + 1];
		}

		cout << "The minimum cutting is " << money << ".
";
	}

	return 0;
}