Chương trình tìm ra chi phí sau khi tìm k chuỗi con duy nhất từ ​​chuỗi cho trước trong C ++

Giả sử, chúng ta có một chuỗi s và một giá trị khác k. Chúng ta phải chọn một số dãy con của s, để chúng ta có thể nhận được k dãy con duy nhất. Ở đây, chi phí chọn một dãy con bằng độ dài của (các) - độ dài của (dãy con). Vì vậy, chúng ta phải tìm tổng chi phí thấp nhất có thể sau khi chọn k dãy con duy nhất. Nếu chúng tôi không thể tìm ra tập hợp này, chúng tôi sẽ trả về -1. Chúng tôi sẽ coi chuỗi trống là chuỗi con hợp lệ.

Vì vậy, nếu đầu vào là s =​​"pqrs", k =4, thì đầu ra sẽ là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s

• Xác định một dp mảng 2D có kích thước (n + 1) x (n + 1) và khởi tạo nó bằng 0

• Xác định một bản đồ cuối cùng

• dp [0, 0]:=1

• để khởi tạo i:=0, khi i

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

  • để khởi tạo j:=(i + 1), khi j> =1, cập nhật (giảm j đi 1), thực hiện -

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

  • nếu s [i] không phải là phần tử cuối của last thì -

    • để khởi tạo j:=0, khi j <=last [s [i]], cập nhật (tăng j lên 1), thực hiện -

      • dp [i + 1, j + 1] - =dp [last [s [i]], j]

  • [s [i]] cuối cùng:=i

• chi phí:=0

• để khởi tạo i:=n, khi i> =0, cập nhật (giảm i đi 1), thực hiện -

  • val:=tối thiểu của k và dp [n, i]

  • chi phí:=cost + (val * (n - i))

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

  • nếu k <=0, thì -

    • Ra khỏi vòng lặp

• nếu k <=0, thì -

  • chi phí trả lại

• trả về -1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào:

"pqrs", 4

Đầu ra

3