Uva 10003 切木棍（dp）

You have to cut a wood stick into pieces. The most affordable company, The Analog Cutting Machinery,Inc. (ACM), charges money according to the length of the stick being cut. Their procedure of workrequires that they only make one cut at a time.It is easy to notice that different selections in the order of cutting can led to different prices. Forexample, consider a stick of length 10 meters that has to be cut at 2, 4 and 7 meters from one end.

Another choice could be cutting at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 =20, which is a better price.

Your boss trusts your computer abilities to nd out the minimum cost for cutting a given stick.

Input

The input will consist of several input cases. The rst line of each test case will contain a positive number l that represents the length of the stick to be cut. You can assume l < 1000. The next line will contain the number n(n<50) of cuts to be made.

The next line consists of n positive numbers ci (0 < ci < l) representing the places where the cuts have to be done, given in strictly increasing order.

An input case with l = 0 will represent the end of the input.

Output

You have to print the cost of the optimal solution of the cutting problem, that is the minimum cost of

cutting the given stick. Format the output as shown below.

SampleInput

100

3

25 50 75

10

4

4 5 7 8

SampleOutput

The minimum cutting is 200.

The minimum cutting is 22.

題意

有一個長為L的棍子，還有n個切割點的位置（按從小到大排列）。你的任務是在這些切割點的位置處把棍子切成n+1部分，使得總切割的費用最少。每次切割的費用等于被切割的木棍長度。例如：L = 10，切割點為2,4,7.如果按照2,4,7來切的話，費用為10+8+6 = 24。

分析

設切割小木棍i~j的最優費用為d（i，j），則d(i,j) = min(d(i,k)+d(k,j)+a[j]-a[i]);

就是求d（0，n+1）即可。邊界條件為：if(i >= j -1) d(i,j) = 0;

用記憶化更易實作。

AC代碼：

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#define MEM(a,x) memset(a,x,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int INF = ;
int dp[][], a[];
int d(int l, int r)
{
    int& ret = dp[l][r];
    if(ret != -) return ret;
    if(l >= r -) return ret = ;
    ret = INF;
    for(int i = l+; i < r; i++)
    {
        ret = min(ret, d(l, i)+d(i, r)+ a[r] - a[l]);
    }
    return ret;
}
int main()
{
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int l;
    while(cin >> l && l)
    {
        int n;
        cin >> n;
        for(int i = ; i <= n; i++)
            cin >> a[i];
        a[] = ;
        a[n+] = l;
        MEM(dp, -);
        printf("The minimum cutting is %d.\n", d(,n+));
    }
    return ;
}