문자열 s와 다른 값 k가 있다고 가정합니다. k개의 고유한 하위 시퀀스를 얻을 수 있도록 s의 일부 하위 시퀀스를 선택해야 합니다. 여기서 부분 시퀀스를 선택하는 비용은 (s)의 길이 - (부분 시퀀스)의 길이와 같습니다. 따라서 k개의 고유한 하위 시퀀스를 선택한 후 가능한 가장 낮은 총 비용을 찾아야 합니다. 이 집합을 찾을 수 없으면 -1을 반환합니다. 빈 문자열을 유효한 하위 시퀀스로 간주합니다.
따라서 입력이 s ="pqrs", k =4와 같으면 출력은 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=s
의 크기 -
(n + 1) x (n + 1) 크기의 2차원 배열 dp 하나를 정의하고 0으로 초기화
-
마지막으로 하나의 지도 정의
-
dp[0, 0] :=1
-
initialize 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]가 last의 끝 요소가 아니면 -
-
j 초기화의 경우:=0, j <=last[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