在 C++ 中找出将整数数组合并为单个值的成本的程序
假设我们有一个包含n个正整数的数组arr。我们还得到了一个整数j。我们必须执行的任务是通过相加将j个数字合并为一个数字。合并的成本等于我们选择的j个数字的相加。我们必须找出这个合并操作的最小可能成本。
因此，如果输入类似于arr=[2,5,6,2,3,1,3],j=4，那么输出将是31。
合并2,3,1,3的成本等于2+3+1+3=9。
合并操作后的数组变为[2,5,6,9]。第二次合并操作的成本等于2+5+6+9=22。因此，合并操作的总成本变为22+9=31。这是最小的合并成本。
示例
让我们看看以下实现以获得更好的理解-
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>& arr, int j) {
int n = arr.size();
if ((n - 1) % (j - 1) != 0) return -1;
vector<int> temp(n + 1);
for (int i = n - 1; i >= 0; i--) {
temp[i] = arr[i] + temp[i + 1];
}
vector<vector<int>> dynArr(n, vector<int>(n));
for (int k = j; k <= n; k++) {
for (int le = 0, rg = k - 1; rg < n; le++, rg++) {
dynArr[le][rg] = INT_MAX;
for (int i = le; i < rg; i += j - 1) {
dynArr[le][rg] = min(dynArr[le][rg], dynArr[le][i] + dynArr[i + 1][rg]);
}
if ((rg - le) % (j - 1) == 0) {
dynArr[le][rg] += temp[le] - temp[rg + 1];
}
}
}
return dynArr[0][n - 1];
}
int main() {
vector<int> arr = {2, 5, 6, 2, 3, 1, 3};
cout<< solve(arr, 4) <<endl;
return 0;
}输入
{2, 5, 6, 2, 3, 1, 3}, 4输出结果31