bool GoodString (int l, int r)
{
int mid = l + r >> 1;
for (int i = 1; i < mid; ++ i)
if (s [i + 1] < s [i]) return 0;
for (int i = l; i <= mid; ++ i)
if (s [i] != s [l + r - i]) return 0;
return 1;
}//O(n)
for (int i = 1; i <= n; ++i)
{
f [i] = INF;
for (int j = 1; j <= i; ++j)//两层 O(n^2)
if (GoodString (j, i)) f [i] = min (f [i], f [j - 1] + 1);
}
:::
其次是拿特解的部分分。
性质 $\text A$ 直接输出 $\text 1$ 就行了，共 $5$ 分，So easy。
性质 $\text B$ 是无相邻字母相同，共 $15$ 分。
好串串是前半段单调不递减，后半段单调不递增的回文串。
性质 $\text B$ 是直接可以当前半段单调递增，后半段单调递减。
因为 $S$ 是小写字符串，所以最多有 $26$ 种字符。
因为只有 $26$ 种字符，所以性质 $B$ 可以只遍历 $51$ 种可能的好串串。
暴力的第二层循环降成 $O(1)$，常数为 $51$。
总时间降成 $O(n^2)$。
性质 $\text C$ 和 $\text B$ 差不多。
第二层需要最少循环次数我当时测了，比 $51$ 小就是了。
接下来思考满分思路（主要优化第二层）。
我们将连续的相同字符合并。
在同一部分内，任何子数组和子数列都满足好串串定义。
中心与 $i$ 在同一部分的分割方案所需次数（单独维护）可以借助上一次状态 $O(1)$ 维护。
因为中间字符相等（回文串），因此好串串中心一定在同一部分内，枚举中心部分就行了。
因为整块满足性质 $B$，可以优化到 $51$ 次。
到这已经可以说是 $O(n)$，但是常数过大，只有 [70分](https://www.luogu.com.cn/record/275355713)。
此时只需考虑中心在不同部分，中间部分左右相同，所以块数定然是单数。
可以让常数锐减到原来的一半，拿 [75分](https://www.luogu.com.cn/record/275355491)。
接着思考，块可以用图像来表示。
$x$ 轴移动的距离表示块的长度。
$y$ 轴的高度表示整个块的字符。
这样可以转换成找 $T$。
要求 $T$ 到 $i$ 的图像是一个左右对称的山峰。
可以得到对于每一个 $i$，最多只有一个 $T$。
找 $T$ 常数为 $26$，时间复杂度为 $O(1)$，[AC记录](https://www.luogu.com.cn/record/275357606)。
当然，这里也可以提前处理优化到常数为 $1$，[AC记录](https://www.luogu.com.cn/record/275367759)。
:::info[Code]
```cpp
#include <iostream>
using namespace std;
class IO {
char ch;
int f;
public :
IO& operator >> (int& a)
{
a = 0, f = 1;
for (ch = getchar (); ch < 48 || 57 < ch; ch = getchar ())
if (ch == '-') f = -1;
for (; 47 < ch && ch < 58; ch = getchar ())
a = (a << 3) + (a << 1) + ch - 48;
a *= f;
return *this;
}
IO& operator >> (char& c)
{
for (c = getchar (); c == ' ' || c == '\n'; c = getchar ());
return *this;
}
IO& operator >> (string& s)
{
s = "";
for (ch = getchar (); ch == ' ' || ch == '\n' || ch == '\r'; ch = getchar ());
for (; ch != ' ' && ch != '\n' && ch != '\r'; ch = getchar ()) s += ch;
return *this;
}
IO& operator << (int a)
{
if (!a) putchar ('0');
else {
int put [35], top = 0;
if (a < 0) putchar ('-'), a = -a;
for (; a;)
put [++top] = a % 10, a /= 10;
for (; top; --top) putchar (put [top] + 48);
}
return *this;
}
IO& operator << (const char&& c)
{
putchar (c);
return *this;
}
IO& operator << (string&& s)
{
for (const char c : s)
putchar (c);
return *this;
}
}IO;
int m, l [5000010], len [5000010];
int C, t, n, f [5000010], nowMinf;
int FirstFeng;
string s;
int ans (int Decl, int Decr)
{
if (Decl < 1) return 0x3f3f3f3f;
int mid = Decl + Decr >> 1;
for (int i = Decr; Decl < mid + i - Decr; -- i)
if (s [l [i - 1]] < s [l [i]]) return 0x3f3f3f3f;
for (int i = Decl + 1; i <= mid; ++ i)
if (s [l [i]] != s [l [Decr + Decl - i]] ||
len [i] != len [Decr + Decl - i]) return 0x3f3f3f3f;
if (s [l [Decl]] != s [l [Decr]] || len [Decl] < len [Decr]) return 0x3f3f3f3f;
return f [l [Decl] + len [Decl] - len [Decr] - 1] + 1;
}
void solve ()
{
n = s.length (), s = " " + s, m = 0, FirstFeng = 0x3f3f3f3f;
for (int i = 1; i <= n; ++ i)
{
if (s [i] == s [i - 1]) ++ len [m], nowMinf = min (nowMinf, f [i - 1]);
else {++ m, l [m] = i, len [m] = 1, nowMinf = f [i - 1];
++ FirstFeng;
if (25 < FirstFeng || m <= FirstFeng) FirstFeng = 0x3f3f3f3f;
if (s [l [m - 1]] < s [l [m]]) FirstFeng = 0;
}
f [i] = nowMinf + 1;
f [i] = min (f [i], ans (m - (FirstFeng << 1), m));
}
IO << f [n] << '\n';
}
signed main ()
{
for (IO >> C >> t; t; -- t)
IO >> s, solve ();
return 0;
}
```
:::
接下来优化 $ans$ 部分。
敏锐的察觉到：
- 我们试图替换 $FirstFeng$ 的第二个 if 判断，
维护了 $m-FirstFeng$ 到 $m$（**后半段**）的单调不递增。
- 对于好串串，**前半段单调不递减** 与 **后半段单调不递增** 等价。
这代表我们可以去掉一个 $O((Decr-Decl) \div 2)$ 的判断（ $(Decr-Decl)) \div 2) \le 26$，可以当做常数），[AC记录](https://www.luogu.com.cn/record/275576596)。
最后我们再把 $ans$ 的第二个判断带入 $O(n)$ 的大循环，并去掉 $ans$ 函数，[AC记录](https://www.luogu.com.cn/record/275579738)。
:::info[Code]
```cpp
#include <iostream>
using namespace std;
class IO {
char ch;
int f;
public :
IO& operator >> (int& a)
{
a = 0, f = 1;
for (ch = getchar (); ch < 48 || 57 < ch; ch = getchar ())
if (ch == '-') f = -1;
for (; 47 < ch && ch < 58; ch = getchar ())
a = (a << 3) + (a << 1) + ch - 48;
a *= f;
return *this;
}
IO& operator >> (char& c)
{
for (c = getchar (); c == ' ' || c == '\n'; c = getchar ());
return *this;
}
IO& operator >> (string& s)
{
s = "";
for (ch = getchar (); ch == ' ' || ch == '\n' || ch == '\r'; ch = getchar ());
for (; ch != ' ' && ch != '\n' && ch != '\r'; ch = getchar ()) s += ch;
return *this;
}
IO& operator << (int a)
{
if (!a) putchar ('0');
else {
int put [35], top = 0;
if (a < 0) putchar ('-'), a = -a;
for (; a;)
put [++top] = a % 10, a /= 10;
for (; top; --top) putchar (put [top] + 48);
}
return *this;
}
IO& operator << (const char&& c)
{
putchar (c);
return *this;
}
IO& operator << (string&& s)
{
for (const char c : s)
putchar (c);
return *this;
}
}IO;
int m, l [5000010], len [5000010];
int C, t, n, f [5000010], nowMinf;
int FirstFeng;
string s;
int ans (int mid, int Decr)
{
int Decl = (mid << 1) - Decr;
if (Decl < 1) return 0x3f3f3f3f;
if (s [l [Decl]] != s [l [Decr]] || len [Decl] < len [Decr]) return 0x3f3f3f3f;
return f [l [Decl] + len [Decl] - len [Decr] - 1] + 1;
}
void solve ()
{
n = s.length (), s = " " + s, m = 0, FirstFeng = 0x3f3f3f3f;
for (int i = 1; i <= n; ++ i)
{
if (s [i] == s [i - 1]) ++ len [m], nowMinf = min (nowMinf, f [i - 1]);
else {
++ m, l [m] = i, len [m] = 1, nowMinf = f [i - 1];
++ FirstFeng;
if (s [l [m - 1]] < s [l [m]]) FirstFeng = 0;
else if (25 < FirstFeng || m <= FirstFeng) FirstFeng = 0x3f3f3f3f;
else {
int L = m - FirstFeng - FirstFeng + 1;
if (s [l [m - 1]] != s [l [L]] ||
len [m - 1] != len [L]) FirstFeng = 0x3f3f3f3f;
}
}
int T = 0x3f3f3f3f, Decl = m - (FirstFeng << 1);
if (0 < Decl && s [l [Decl]] == s [l [m]] && len [m] <= len [Decl])
T = f [l [Decl] + len [Decl] - len [m] - 1] + 1;
f [i] = min (nowMinf + 1, T);
}
IO << f [n] << '\n';
}
signed main ()
{
for (IO >> C >> t; t; -- t)
IO >> s, solve ();
return 0;
}
```
:::