UVa 10003 Cutting Sticks（区间DP）

题意：

给定一个l长得木棍，要把它从给定的n个点截断，每截断一次需要的费用为木棍的长度。

求截断这个木棍所要花费的最小代价。

思路：

典型的区间DP，要额外添加2个点：0和l，于是区间从1不断扩展到n+1，dp[i][j]代表点i到点j所要花费的最小代价。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

#define min(a,b) (((a) < (b)) ? (a) : (b))

const int INF = 1e9;
int a[60];
int dp[60][60];

int main()
{
    int l, n;
    while (scanf("%d", &l) && l)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);

        a[0] = 0, a[n+1] = l;
        n += 1;

        memset(dp, 0, sizeof(dp));

        for (int i = 0; i <= n; ++i)
        {
            for (int j = 0; j <= n; ++j)
                dp[i][j] = INF;
            dp[i][i] = 0;
        }

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

        for (int p = 2; p <= n; ++p)
            for (int i = 0, j = p; j <= n; ++i, ++j)
                for (int k = i; k < j; ++k)
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[j] - a[i]);

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