在C ++中从给定字符串中找到k个唯一子序列后查找成本的程序
假设我们有一个字符串s和另一个值k。我们必须选择s的一些子序列，以便获得k个唯一的子序列。在此，选择子序列的成本等于(s)的长度-（子序列的）长度。因此，我们必须在选择k个唯一子序列后找到最低的总成本。如果我们无法找到该集合，则将返回-1。我们将空字符串视为有效的子序列。
因此，如果输入类似于s=“pqrs”，k=4，则输出将为3。
在线示例
让我们看下面的实现以更好地理解-
#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