ต้นทุนขั้นต่ำในการผสานหินใน C++

สมมุติว่าเรามีกองหิน N กองเรียงกันเป็นแถว ที่นี่กองที่ i มีหินจำนวน [i] ของหิน การย้ายประกอบด้วยการรวมกอง K ที่ต่อเนื่องกันเป็นกองเดียว ตอนนี้ค่าใช้จ่ายในการย้ายนี้เท่ากับจำนวนหินทั้งหมดในจำนวน K เหล่านี้ เราต้องหาต้นทุนขั้นต่ำในการรวมกองหินทั้งหมดให้เป็นกองเดียว หากไม่มีวิธีแก้ปัญหาดังกล่าว ให้คืนค่า -1

ดังนั้น หากอินพุตเป็น [3,2,4,1] และ K =2 เอาต์พุตจะเป็น 20 นั่นเป็นเพราะเราจะเริ่มด้วย [3, 2, 4, 1] จากนั้นเรารวม [3, 2] ในราคา 5 และเราเหลือ [5, 4, 1] หลังจากนั้นเรารวม [4, 1] ในราคา 5 และเหลือ [5, 5] จากนั้นเรารวม [5, 5] ด้วยราคา 10 และเราเหลือ [10] ดังนั้น ค่าใช้จ่ายทั้งหมดคือ 20 และนี่คือราคาขั้นต่ำ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของหิน

• ถ้า (n - 1) mod (k - 1) ไม่เท่ากับ 0 แล้ว −

  • กลับ -1

• กำหนดคำนำหน้าอาร์เรย์ขนาด n + 1

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • คำนำหน้า[i] :=คำนำหน้า[i - 1] + หิน[i - 1]

• กำหนดอาร์เรย์ 2 มิติ dp หนึ่งขนาด n x n

• สำหรับการเริ่มต้นความยาว :=k เมื่อความยาว <=n อัปเดต (เพิ่มความยาว 1) ทำ -

  • สำหรับการเริ่มต้น i :=0, j :=length - 1, เมื่อ j

  • dp[i, j] :=inf

  • สำหรับการเริ่มต้น mid :=i เมื่อ mid

    • dp[i, j] :=ขั้นต่ำของ dp[i, j] และ dp[i, mid] + dp[mid + 1, j]

  • ถ้า (j - i) mod (k - 1) เท่ากับ 0 แล้ว −

    • dp[i, j] :=dp[i, j] + คำนำหน้า[j + 1] - คำนำหน้า[i]

• กลับ dp[0, n - 1]

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int mergeStones(vector<int>& stones, int k){
      int n = stones.size();
      if ((n - 1) % (k - 1) != 0)
      return -1;
      vector<int> prefix(n + 1);
      for (int i = 1; i <= n; i++) {
         prefix[i] = prefix[i - 1] + stones[i - 1];
      }  
      vector<vector<int>> dp(n, vector<int>(n));
      for (int length = k; length <= n; length++) {
         for (int i = 0, j = length - 1; j < n; i++, j++) {
            dp[i][j] = INT_MAX;
            for (int mid = i; mid < j; mid += k - 1) {
               dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid +
               1][j]);
            }
            if ((j - i) % (k - 1) == 0) {
               dp[i][j] += prefix[j + 1] - prefix[i];
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,4,1};
   cout << (ob.mergeStones(v, 2));
}

อินพุต

{3,2,4,1}, 2

ผลลัพธ์

20