Phân Hoạch Xâu Đối Xứng

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho một xâu ký tự $S$ chỉ gồm các chữ cái tiếng Anh in thường. Hãy tìm số lượng xâu con đối xứng ít nhất sao cho có thể phân hoạch $S$ thành các xâu con liên tiếp mà mỗi xâu con đều là xâu đối xứng.

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ố lượng xâu con đối xứng ít nhất.

Ví dụ
Input Output
aab 2
Giới hạn
  • $1 \le |S| \le 1000$.
Draft saved