CTDL và giải thuật - Giải thuật Qui hoạch động
Một chuỗi s
được gọi là đối xứng nếu khi viết ngược s
lại thì s
vẫn không thay đổi, ví dụ "1221"
, "232"
là chuỗi đối xứng, còn"123"
không là chuỗi đối xứng.
Cho một chuỗi s
, hãy xóa một số ký tự trong s
để được một chuỗi đối xứng dài nhất. Nếu có thể tạo được nhiều chuỗi đối xứng cùng độ dài thì đưa ra chuỗi đầu tiên.
Ví dụ:
- Test mẫu 1:
Input Output aabbsca abba
Vớis = "aabbsca"
thìlongestPalindrome(s) = "abba"
.
Giải thích: Chúng ta sẽ xóa các ký tự'a', 's'
và'c'
.
- Test mẫu 2:
Input Output 123a 1
Vớis = "123a"
thìlongestPalindrome(s) = "1"
.
Hướng dẫn bài tập.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
using namespace std;
int l[1001][1001];
string longestChainSymmetry(string s)
{
string x = s;
string y = "";
for (int i = s.length() - 1; i >= 0; i --) y = y + x[i];
int m = x.length(), n = y.length();
x = ' ' + x;
y = ' ' + y;
for (int i = 0; i <= m; i++) l[i][0] = 0;
for (int j = 0; j <= n; j++) l[0][j] = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (x[i] == y[j]) l[i][j] = l[i-1][j-1] + 1;
else l[i][j] = max(l[i-1][j], l[i][j-1]);
}
string p = "";
while (l[m][n] > 0 && m > 0 && n > 0){
while (l[m-1][n] == l[m][n]) m --;
while (l[m][n] == l[m][n-1]) n --;
p = x[m] + p;
m --;
n --;
}
return p;
}
int main(){
string s;
getline(cin, s);
cout << longestChainSymmetry(s);
return 0;
}