请用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
时间: 2024-02-22 10:59:14 浏览: 161
以下是 C++ 代码实现,采用动态规划思想:
```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)$。
阅读全文