Đề bài

Palindrome là xâu ký tự mà nếu đọc nó từ trái sang phải cũng như từ phải sang trái ta được cùng một xâu. Một xâu ký tự bất kỳ luôn có thể biểu diễn như là một dãy các palindrome nếu như ta coi xâu chỉ gồm một ký tự luôn là một palindrome. Ví dụ: xâu bobseesanna có thể biểu diễn dưới dạng dãy các palindrome theo nhiều cách, chẳng hạn:

• bobseesanna = bob + sees + anna
• bobseesanna = bob + s + ee + s + anna
• bobseesanna = b +o + b + sees + a + n + n + a.

Cho xâu ký tự $S$, cần tìm cách biểu diễn xâu dưới dạng một dãy gồm số ít nhất các palindrome. Ví dụ: cho bobseesanna, do ta có bobseesanna = bob + sees + anna và không thể biểu diễn bobseesanna bởi ít hơn là palindrome nên biểu diễn này chính là biểu diễn cần tìm.

Dữ liệu vào:

• Gồm một dòng chứa xâu ký tự chỉ gồm các chữ cái latin thường.

Dữ liệu ra:

• Gồm một dòng duy nhất ghi số lượng ít nhất các palindrome trong biểu diễn tìm được.

Ví dụ:

// Input

bobseesanna

// Output

3

Giới hạn:

• Độ dài xâu $S$ không quá $255$ ký tự.

Nhận xét:

• Đối với quy hoạch động, ta sẽ dựa trên kết quả của các bài toán con đã tính được từ trước, tức là chỉ cần tính được phần tử đang xét từ các phần tử đã tính được từ trước trong mảng và cứ thế lặp lại từ bài toán đơn giản đến bài toán lớn thoả mãn yêu cầu bài toán.
• Gọi $f[i]$ là số palindrome ít nhất phân tích được của i chữ cái đầu tiên của xâu $S$, ta có một số trường hợp như sau:
  • $f[1] = 1$ vì chỉ có $1$ kí tự.
  • Ta tách $i$ kí tự kể từ $1$ của xâu $s$ thành $i - 1$ kí tự đầu tiên và $1$ kí tự thứ $i$, khi đó số palindrome phân tích được là: $f[i] = f[i-1] + 1$
  • Ta xét kí tự thứ $j$, $(1 <= j < i)$ nếu $s[j] = s[i]$ và các kí tự kể từ $j + 1$ cho đến $i - 1$ hợp lại thành một chuỗi palindrome thì ta có số palindrome ít nhất phân tích được là: $f[i] = f[j-1] + 1$, trong đó $f[j-1]$ là số palindrome ít nhất phân tích từ $j - 1$ kí tự đầu tiên của xâu $S$, ta cộng thêm $1$ bởi thêm một palindrome (đống kí tự từ $j$ cho đến $i$).
• Tóm lại, ta có công thức QHĐ: $$\begin{cases} f[1] = 1 \\ f[i] = f[i-1] + 1 \\ f[i] = min(f[i], f[j-1] + 1) &\text{Nếu s[j] + s[j+1] + ... + s[i] là palindrome} \end{cases}$$

Hàm kiểm tra palindrome

bool check(int L, int R){ 
    string s1 = "", s2 = "";
    for (int i = L; i<= R; i++)
        s1 = s1 + s[i];
    for (int i = R; i >= L; i--)
        s2 = s2 + s[i];
    if (s1 == s2) return true;
    else return false;
}

Giải thích

• Ta kiểm tra palindrome đúng như theo đầu bài.

Full code

#include <bits/stdc++.h>
#define MAX 100004
#define INF (int)(1e9)
#define pii pair<int, int>
#define piii pair<int, pii>
using namespace std;
char s[258];
int f[258];
int n;
bool check(int L, int R){
    string s1 = "", s2 = "";
    for (int i = L; i<= R; i++)
        s1 = s1 + s[i];
    for (int i = R; i >= L; i--)
        s2 = s2 + s[i];
    if (s1 == s2) return true;
    else return false;
}
int main()
{
    scanf("%s", s + 1); //Đọc dữ liệu vào mảng char, bắt đầu từ 1
    n = strlen(s + 1); //Lấy độ dài của mảng, tính từ 1
    f[1] = 1;

    for (int i = 2; i<=n; i++) {
        f[i] = f[i-1] + 1;
        for (int j = i-1; j>= 1; j--)
            if (s[i] == s[j])
                if (check(j + 1, i - 1) == true)
                    f[i] = min(f[i], f[j-1] + 1);
    }
    cout << f[n];
    return 0;
}

Nguồn bài tập: Chuyên Sơn La Online Judge

Thiết kế thuật giải: Bấm vào đây