Chia xâu đối xứng ít nhát cắt
Points
32
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề 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$.
Community Discussion