資料結構
網路
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 次檢視
廣告