โปรแกรมค้นหาต้นทุนหลังจากค้นหา k ลำดับต่อมาที่ไม่ซ้ำจากสตริงที่ระบุใน C++

สมมติว่าเรามีสตริง s และอีกค่าหนึ่งคือ k เราต้องเลือกลำดับย่อยของ s เพื่อเราจะได้ k ลำดับย่อยเฉพาะ ที่นี่ค่าใช้จ่ายในการเลือกลำดับย่อยเท่ากับความยาวของ (s) - ความยาวของ (ส่วนต่อท้าย) ดังนั้น เราต้องหาต้นทุนรวมที่ต่ำที่สุดที่เป็นไปได้หลังจากเลือก k รายการย่อยที่ไม่ซ้ำ หากเราไม่สามารถหาชุดนี้ได้ เราจะคืนค่า -1 เราจะถือว่าสตริงว่างเป็นผลสืบเนื่องที่ถูกต้อง

ดังนั้น หากอินพุตเป็น s ="pqrs", k =4 เอาต์พุตจะเป็น 3

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

• n :=ขนาดของ s

• กำหนดขนาดอาร์เรย์ 2 มิติหนึ่ง dp (n + 1) x (n + 1) และเริ่มต้นด้วย 0

• กำหนดหนึ่งแผนที่สุดท้าย

• dp[0, 0] :=1

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

  • dp[i + 1, 0] :=1

  • สำหรับการเริ่มต้น j :=(i + 1) เมื่อ j>=1 อัปเดต (ลด j โดย 1) ทำ -

    • dp[i + 1, j] :=dp[i, j] + dp[i, j - 1]

  • ถ้า s[i] ไม่ใช่องค์ประกอบสุดท้ายแล้ว −

    • สำหรับการเริ่มต้น j :=0 เมื่อ j <=ล่าสุด[s[i]] อัปเดต (เพิ่ม j ทีละ 1) ทำ -

      • dp[i + 1, j + 1] - =dp[สุดท้าย[s[i]], j]

  • สุดท้าย[s[i]] :=i

• ราคา :=0

• สำหรับการเริ่มต้น i :=n เมื่อ i>=0, อัปเดต (ลด i โดย 1) ทำ -

  • val :=ขั้นต่ำของ k และ dp[n, i]

  • ราคา :=ราคา + (val * (n - i))

  • k :=k - dp[n, i]

  • ถ้า k <=0 แล้ว −

    • ออกจากวง

• ถ้า k <=0 แล้ว −

  • ค่าส่งคืน

• กลับ -1

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
int solve(string s, int k) {
   int n = s.size();
   vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
   unordered_map<char, int> last;
   dp[0][0] = 1;
   for (int i = 0; i < n; i++) {
      dp[i + 1][0] = 1;
      for (int j = (i + 1); j >= 1; j--) {
         dp[i + 1][j] = dp[i][j] + dp[i][j - 1];
      }
      if (last.find(s[i]) != last.end()) {
         for (int j = 0; j <= last[s[i]]; j++) {
            dp[i + 1][j + 1] -= dp[last[s[i]]][j];
         }
      }
      last[s[i]] = i;
   }
   int cost = 0;
   for (int i = n; i >= 0; i--) {
      int val = min(k, dp[n][i]);
      cost += (val * (n - i));
      k -= dp[n][i];
      if (k <= 0) {
         break;
      }
   }
   if (k <= 0) {
      return cost;
   }
   return -1;
}
int main(){
   cout << solve("pqrs",4) << endl;
   return 0;
}

อินพุต:

"pqrs", 4

ผลลัพธ์

3