โปรแกรมค้นหาโครงสร้างการแยกวิเคราะห์ขั้นต่ำใน C++

สมมติว่าเรามีรายการของตัวเลขที่ไม่ซ้ำกันและเรียงลำดับที่แสดงถึงเบรกพอยต์ในสตริง เราต้องการสร้างต้นไม้จากกฎเหล่านี้ -

• มีโหนดที่มีค่า (a, b) โดยที่ a และ b เป็นเบรกพอยต์ ซึ่งหมายความว่าโหนดมีช่วงจากดัชนี [a, b] ในสตริง

• โหนดรูทครอบคลุมทุกเบรกพอยต์ (ทั้งสตริง)

• สแปนของโหนดย่อยซ้ายและขวาถูกเรียงลำดับ ต่อเนื่องกัน และมีสแปนของโหนดหลัก

• ดัชนีของโหนดลีฟของ 'a' ในเบรกพอยต์คือ 1 ก่อนดัชนีของ 'b' ในส่วนเบรกพอยต์

ราคาของต้นไม้ถูกกำหนดเป็นผลรวมของ b - a สำหรับทุกโหนดในทรี เป้าหมายของเราคือการกำหนดราคาต้นไม้ที่เป็นไปได้ต่ำที่สุดเท่าที่จะเป็นไปได้

ดังนั้น หากอินพุตเป็นเหมือนเบรกพอยต์ =[1, 4, 7, 12] เอาต์พุตจะเป็น 28

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

• n :=ขนาดของเบรกพอยต์อาร์เรย์อินพุต

• ถ้า n <=1 แล้ว −

  • คืนค่า 0

• ถ้า n เท่ากับ 2 แล้ว −

  • จุดพักกลับ[1] - จุดพัก[0]

• กำหนดอาร์เรย์ p[n - 1]

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

  • p[i] :=เบรกพอยต์[i + 1]

• กำหนดอาร์เรย์ก่อน[n]

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

  • pre[i] :=pre[i - 1] + p[i - 1]

• กำหนดอาร์เรย์ 2 มิติ dp[n, n] หนึ่งรายการและเริ่มต้นคอลัมน์ด้วยความไม่มีที่สิ้นสุด

• กำหนดอาร์เรย์ 2 มิติ op[n, n]

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

  • dp[i,i] :=p[i - 1], op[i,i] :=ผม

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

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

    • j :=i + len - 1

    • idx :=ผม

    • สำหรับการเริ่มต้น k :=สูงสุดของ(i, op[i,j-1]) เมื่อ k <ขั้นต่ำของ (j - 1, op[i + 1, j]), อัปเดต (เพิ่ม k ขึ้น 1) ทำ:

      • ราคา :=dp[i, k] + dp[k + 1, j]

      • ถ้าราคา

        • idx :=k

        • dp[i, j] :=ต้นทุน

    • op[i, j] :=idx

    • dp[i, j] :=dp[i, j] + ก่อน[j] - ก่อน[i - 1]

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

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& breakpoints) {
   int n = breakpoints.size();
   if (n <= 1) return 0;
   if (n == 2) return breakpoints[1] - breakpoints[0];
      vector<int> p(n - 1);
   for (int i = 0; i < n - 1; ++i) p[i] = breakpoints[i + 1] - breakpoints[i];
      vector<int> pre(n);
   for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] + p[i - 1];
      vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
      vector<vector<int>> op(n, vector<int>(n));
   for (int i = 1; i < n; ++i) dp[i][i] = p[i - 1], op[i][i] = i;
   for (int len = 2; len < n; ++len) {
      for (int i = 1; i + len - 1 < n; ++i) {
         int j = i + len - 1;
         int idx = i;
         for (int k = max(i, op[i][j - 1]); k <= min(j - 1, op[i + 1][j]); ++k) {
            int cost = dp[i][k] + dp[k + 1][j];
            if (cost < dp[i][j]) {
               idx = k;
               dp[i][j] = cost;
            }
         }
         op[i][j] = idx;
         dp[i][j] += pre[j] - pre[i - 1];
      }
   }
   return dp[1][n - 1];
}
int main(){
   vector<int> breakpoints = {1, 4, 7, 12};
   cout << solve(breakpoints) << endl;
   return 0;
}

อินพุต

{1, 4, 7, 12}

ผลลัพธ์

28