← 返回题单

题单练习区间型DP入门

← 上一题下一题 →

A6933 | $Alice 的回文串$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的字符串 $s$（仅包含小写字母）。你可以进行若干次操作： 每次选择 $s$ 的一个回文子串（长度 $\ge 1$）并将其整个删除，剩余部分按原相对顺序拼接在一起。 请计算将整个字符串删除所需的最少操作次数。 回文串指正读和反读相同的字符串，例如 a、aba、abba。

输入格式

一行一个字符串 $s$

输出格式

输出一个整数，表示最少操作次数。

输入输出样例

输入 #1

abba

输出 #1

输入 #2

abca

输出 #2

输入 #3

abc

输出 #3

数据范围 $1 \le n = |s| \le 600$； 字符集：a–z（小写字母）。 测试点与数据范围 测试点$n$ 范围$1$~$2$$n \le 30$$3$~$4$$n \le 200$$5$~$20$$n \le 600$

C++ 编辑器

输入

输出