UVA - 10003Cutting Sticks（遞推）

UVA - 10003Cutting Sticks（遞推）

題目：UVA - 10003Cutting Sticks（遞推）

題目大意：給根木棍長度l，現在要鋸這根木棍，給出n個鋸點，求怎樣鋸才能使得開銷最小。例如 長度為10的木棍， 鋸點2 4 7，那麼如果按照這個順序 ， 首先顯示由長度位10的木頭先鋸了2 ，開銷就加10，然後鋸完現在有【0，2】和【2，10】長度分別為2 ，8的木棍，現在要在4這個位置鋸木頭，就是在長度為8的木頭上鋸4這個位置，這樣就加上8，然後又有長度為【2，4】【4，10】的木頭，最後要鋸7的話，就需要開銷加上6.所以開銷就是10 + 8 + 6 = 24；順序4 2 7的話：開銷：10 + 4 + 6 = 20;所以要求最小的開銷。

解題思路：之前的想法，長度為l的木頭，先挑個地方鋸的話，就會產生另外兩根，這樣就應該從長的開始推短的。但是後面發現從短的推長的也是一樣的，因為短的組成長的，和長的鋸成短的是一樣的，最後只要加上這個長的木棍的長度（也就是開銷）。狀態轉移方程：dp【i】【j】：代表組成鋸點i到鋸點j這個木棍的最小開銷。dp【i】【j】 = Min (dp[i][k] + dp[k][j] + j - i) k> i && k < j) 相鄰的鋸點是代表這個木棍不能在鋸了，所以dp【i】【i + 1】 = 0；

代碼：

#include 
#include 

typedef long long ll;

const int maxn = 1005;
const int N = 55;
const int INF = 0x3f3f3f3f;

ll dp[maxn][maxn];
int v[N];
int l, n;

void init () {

	v[n + 1] = l;
	v[0] = 0;
	for (int i = 0; i <= n; i++) 
		dp[v[i]][v[i + 1]] = 0;
}

ll Min (const ll a, const ll b) { return a < b? a: b; }

int main () {

	while (scanf ("%d", &l), l) {

		scanf ("%d", &n);

		for (int i = 1; i <= n; i++)
			scanf ("%d", &v[i]);

		init ();
		ll temp;
		for (int i = 2; i <= n + 1; i++)
			for (int j = 0; j + i <= n + 1; j++) {
				
				temp = INF;
				for (int k = 1; k < i; k++)
					temp = Min (temp, dp[v[j]][v[j + k]] + dp[v[j + k]][v[j + i]]);
				dp[v[j]][v[j + i]] = temp + v[j + i] - v[j];
			}

		printf ("The minimum cutting is %lld.\n", dp[0][l]);
	}
	return 0;
}