数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律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。这是最小合并成本。
为了解决这个问题，我们将遵循以下步骤：
- n := arr的大小
- 如果(n - 1) mod (j - 1)不等于0，则：
- 返回-1
- 定义一个数组temp(n + 1)
- 从i := n - 1开始，当i >= 0时，更新(i递减1)，执行：
- temp[i] := arr[i] + temp[i + 1]
- 定义一个n x n阶的二维数组dynArr
- 从k := j开始，当k <= n时，更新(k递增1)，执行：
- 从le := 0，rg := k - 1开始，当rg < n时，更新(le递增1)，(rg递增1)，执行：
- dynArr[le, rg] := inf
- 从i := le开始，当i < rg时，更新i := i + j - 1，执行：
- dynArr[le, rg] := min(dynArr[le, rg] 和 dynArr[le, i] + dynArr[i + 1, rg])
- 如果(rg - le) mod (j - 1)等于0，则：
- dynArr[le, rg] := dynArr[le, rg] + temp[le] - temp[rg + 1]
- 返回dynArr[0, n - 1]
示例
让我们看看以下实现，以便更好地理解：
#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
更新于： 2021年10月19日
83 次查看
广告