Giả sử ta có chuỗi s và giá trị k. Ta phải chọn các dãy con của s để có k dãy con duy nhất. Chi phí chọn một dãy con = độ dài(s) - độ dài(dãy con). Ta phải tìm tổng chi phí thấp nhất có thể. Nếu không thể, trả về -1. Chuỗi rỗng được coi là dãy con hợp lệ.
Ví dụ: s = "pqrs", k = 4, đầu ra = 3.
Để giải quyết, ta dùng quy hoạch động:
- n := độ dài s.
- Định nghĩa mảng dp 2D kích thước (n+1)x(n+1), điền 0.
- Định nghĩa map last.
- dp[0][0] := 1.
- for i từ 0 đến n-1:
- dp[i+1][0] := 1.
- for j từ i+1 xuống 1:
- dp[i+1][j] := dp[i][j] + dp[i][j-1].
- Nếu s[i] có trong last:
- for j từ 0 đến last[s[i]]: dp[i+1][j+1] -= dp[last[s[i]]][j].
- last[s[i]] := i.
- cost := 0.
- for i từ n xuống 0:
- val = min(k, dp[n][i]).
- cost += val * (n - i).
- k -= dp[n][i].
- Nếu k <= 0: break.
- Nếu k <= 0: trả cost; ngược lại trả -1.
Ví dụ
Xem triển khai dưới đây:
#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