C++代码  
  1. //  [解题方法]   
  2. //  记忆化搜索（递归，子问题的结果用备忘录存起来，避免重复求解）   
  3. //  设棍子长度n，输入的c[i]是棍子上的坐标   
  4. //  dp[x][y](即dfs(x,y))表示砍c[x]到c[y]段的最小花费   
  5. //  每次砍c[x]~c[y]段的时候枚举砍的位置i   
  6. //  状态转移：dp[x][y] = min(dp[x][i] + dp[i][y] + c[y]-c[x])(x<=i<=y)   
  7. //  注：-1表示无穷大   
  8.   
  9. #include <iostream>   
  10. #include <string.h>   
  11. #include <stdio.h>   
  12. #include <stdlib.h>   
  13. #include <algorithm>   
  14. using namespace std;   
  15. #define LL long long   
  16. #define M 55   
  17. #define inf 0x3fffffff   
  18.   
  19. int dp[M][M], c[M];   
  20.   
  21. int dfs (int x, int y)   
  22. {   
  23.     if (dp[x][y] > -1)   
  24.         return dp[x][y];   
  25.     int tp = -1, i;   
  26.     for (i = x+1; i < y; i++)   
  27.     {   
  28.         int tmp = dfs(x, i) + dfs(i, y) + c[y] - c[x];   
  29.         if (tp < 0 || tmp < tp) tp = tmp;   
  30.     }   
  31.     return (dp[x][y] = tp);   
  32. }   
  33.   
  34. int main()   
  35. {   
  36.     int n, m, i;   
  37.     while (cin >> n, n)   
  38.     {   
  39.         cin >> m;   
  40.         c[0] = 0;   
  41.         for (i = 1; i <= m; i++) {   
  42.             cin >> c[i];   
  43.         }   
  44.         c[m+1] = n;   
  45.         memset (dp, -1, sizeof(dp));   
  46.         for (i = 0; i <= m; i++)   
  47.             dp[i][i+1] = 0;   
  48.         cout << "The minimum cutting is " << dfs(0, m+1) << "." << endl;   
  49.     }   
  50.     return 0;   
  51. }