Chia xâu đối xứng ít nhát cắt

Buổi 22 — DP 2D & LIS Dynamic Programming Strings
Points
32
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho một xâu ký tự $S$ độ dài $N$ chỉ gồm các chữ cái tiếng Anh in thường. Bạn cần cắt xâu $S$ thành các xâu con liên tiếp sao cho mỗi xâu con đều là xâu đối xứng (palindrome). Hãy tìm số nhát cắt ít nhất cần thực hiện.

Cấu trúc con tối ưu: tiền xử lý mảng $isPal[l][r]$ trong $O(N^2)$, sau đó $dp[i] = \min_{j \le i, isPal[j][i]} (dp[j-1] + 1)$.

Dữ liệu vào

Một dòng duy nhất chứa xâu $S$.

Dữ liệu ra

Một số nguyên duy nhất là số nhát cắt ít nhất.

Ví dụ
Input Output
aab 1
abacaba 0
Giới hạn

$1 \le |S| \le 3000$.

Draft saved