题目：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; }