请用c++代码实现题目背景 您必须将木棍切成碎片。最便宜的公司是 Analog Cutting Machinery，Inc.（ACM），它 根据要切割的木棍的长度收费。 题目描述 他们的工作程序要求他们一次只能切割一个。 容易注意到，按切割顺序进行的不同选择会导致不同的价格。例如，考虑一根长度为 10 米 的木棒，必须从一端将其切成 2、4 和 7 米。有几种选择。一个可以先在 2 处切削，然后在 4 处切削，然后在 7 处切削。这导致价格为 10 + 8 + 6 = 24，因为第一根木棍的长度为 10 米，其结果为 8 米，最后一根为 6 米。另一个选择可能是削减 4，然后削减 2，然后削减 7。 这将导致价格 10 + 4 + 6 = 20，这是一个更好的价格。 您的老板信任您的计算机能力，以找出切割给定木棍的最低成本。 输入格式 输入将包含几个输入案例。每个测试用例的第一行将包含一个正数 L，代表要切割的棒的长度。您可以假设 L <1000。 下一行将包含 要进行的切割数量 n （ n <50）。 下一行由 n 个 正数 c i （0 < c i < l）组成，代表必须进行切割的位置，并以严格的递增顺序给出。 L = 0 的输入条件 表示输入的结尾。 输出格式 您必须打印出解决切割问题的最佳方法的成本，即切割给定棒的最低成本。 输入输出样例 输入 #1复制 100 3 25 50 75 10 4 4 5 7 8 0 输出 #1复制 200 22

以下是 C++ 代码实现，采用动态规划思想：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 55;

int l, n;
int c[N];
int f[N][N];

int main()
{
    while (cin >> l, l)
    {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> c[i];
        c[n + 1] = l;

        memset(f, 0x3f, sizeof f);
        for (int i = 1; i <= n + 1; i ++ ) f[i][i - 1] = 0;

        for (int len = 2; len <= n + 1; len ++ )
            for (int i = 1; i <= n - len + 2; i ++ )
            {
                int j = i + len - 1;
                for (int k = i; k < j; k ++ )
                    f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + c[j] - c[i - 1]);
            }

        cout << "The minimum cutting is " << f[1][n + 1] << "." << endl;
    }

    return 0;
}

时间复杂度：$O(n^3)$。