โปรแกรมหาต้นทุนขั้นต่ำในการรวมอาเรย์จำนวนเต็มใน C++

สมมติว่าเราได้รับอาเรย์ arr ที่มี n จำนวนเต็มบวก รวมถึงจำนวนเต็ม 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
• คำนวณผลรวมสะสมจากท้าย: temp[i] := arr[i] + temp[i + 1]
• สร้างอาเรย์ 2 มิติ dynArr ขนาด n x n
• วนลูป k จาก j ถึง n:
  • วนลูป le จาก 0, rg = k - 1 จนกว่า rg < n:
    • dynArr[le][rg] := INF
    • วนลูป i จาก le ถึง rg - 1 ก้าว 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] += 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