โปรแกรมหาค่าใช้จ่ายในการรวมอาร์เรย์ของจำนวนเต็มเป็นค่าเดียวใน 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
• กำหนดอาร์เรย์ชั่วคราว (n + 1)
• สำหรับการเริ่มต้น i :=n - 1 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ทำ −
  • อุณหภูมิ[i] :=arr[i] + อุณหภูมิ[i + 1]
• กำหนด dynArr อาร์เรย์ 2 มิติหนึ่งรายการของคำสั่ง n x n
  • สำหรับการเริ่มต้น k :=j เมื่อ k <=n อัปเดต (เพิ่ม k ขึ้น 1) ทำ −
  • สำหรับการเริ่มต้น le :=0, rg :=k - 1 เมื่อ rg
  • dynArr[le, rg] :=inf
  • สำหรับการเริ่มต้น i :=le เมื่อฉัน
  • dynArr[le, rg] :=ขั้นต่ำของ (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]

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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