UVa 10003

　　题目大意：有一根长l的木棍，有n个切割点要把这根木棍切成n+1段，知道n个切割点的位置。切割一段长度为d的木棍需要的花费为d，如一段长度为10的木棍，有3个切割点：2，5，7，如果按切割点位置从左到右进行切割，所需花费为10+8+5。找出合理的切割顺序使得花费最小。

　　想到了最优矩阵链乘...dp，使用自顶向下带备忘的dp方法，cost[left][right]记录切割从第left个切割点到第right个切割点所需的最小花费。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <climits>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int cost[55][55], a[55];
 8 
 9 int cut(int left, int right)
10 {
11     if (cost[left][right] >= 0)  return cost[left][right];
12     if (left + 1 == right)  return 0;
13     int lmin = INT_MAX;
14     for (int i = left+1; i < right; i++)
15         lmin = min(lmin, cut(left, i)+cut(i, right)+a[right]-a[left]);
16     return cost[left][right] = lmin;
17 }
18 
19 int main()
20 {
21 #ifdef LOCAL
22     freopen("in", "r", stdin);
23 #endif
24     int l;
25     while (scanf("%d", &l) && l)
26     {
27         int n;
28         scanf("%d", &n);
29         a[0] = 0;
30         for (int i = 1; i <= n; i++)
31             scanf("%d", &a[i]);
32         a[n+1] = l;
33         memset(cost, -1, sizeof(cost));
34         int ans = cut(0, n+1);
35         printf("The minimum cutting is %d.
", ans);
36     }
37     return 0;
38 }

View Code

　　开始在cut函数内忘记给cost[][]保存值了，结果TLE了，还纳闷为什么会超时呢...