資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式：查詢給定字串中k個唯一子序列後的成本
假設我們有一個字串s和另一個值k。我們必須選擇s的一些子序列，以便我們可以得到k個唯一的子序列。這裡，選擇子序列的成本等於s的長度 - 子序列的長度。因此，我們必須找到在選擇k個唯一子序列後可能的最低總成本。如果我們無法找到這個集合，我們將返回-1。我們將空字串視為有效的子序列。
因此，如果輸入類似於s = "pqrs"，k = 4，則輸出將為3。
為了解決這個問題，我們將遵循以下步驟：
n := s的長度
定義一個大小為(n + 1) x (n + 1)的二維陣列dp，並將其初始化為0
定義一個對映last
dp[0, 0] := 1
初始化i := 0，當i < n時，更新（i遞增1），執行：
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]不是last的末尾元素，則：
初始化j := 0，當j <= last[s[i]]時，更新（j遞增1），執行：
dp[i + 1, j + 1] -= dp[last[s[i]], j]
last[s[i]] := i
cost := 0
初始化i := n，當i >= 0時，更新（i遞減1），執行：
val := k和dp[n, i]的最小值
cost := cost + (val * (n - i))
k := k - dp[n, i]
如果k <= 0，則：
退出迴圈
如果k <= 0，則：
返回cost
返回-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
更新於：2020年12月23日
瀏覽量：137
廣告