題目: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; }