题目大意

给定一个字符串 $S$（只包含大写字母），可以删除任意字符并重新排列剩余字符，要求组成一个单词。单词由若干个音节拼接而成，每个音节的结构为：
辅音 + 元音 + 辅音（按顺序）。

特殊规则：

• 字母 A, E, I, O, U 只能作元音。
• 字母 Y 可以作元音或辅音。
• 其余字母（除 A, E, I, O, U, Y 外）只能作辅音。
• 字符串 "NG" 作为一个整体可以当作一个辅音（即两个字母 N 和 G 连在一起视为一个辅音单位）。

求能组成的最长单词的长度（即所用字母的总数），若无法组成任何单词则输出 $0$。

解题思路

1. 基本统计

设原始字符串中：

• $V_0$：普通元音（A, E, I, O, U）的个数。
• $C_0$：普通辅音（除 A, E, I, O, U, Y, N, G 外的字母）的个数。
• $Y$：字母 Y 的个数。
• $N$：字母 N 的个数。
• $G$：字母 G 的个数。

2. 决策变量

由于 Y 可以扮演两种角色，N 和 G 可以单独使用或组合成 "NG" 辅音单位，我们需要枚举：

• $x$：使用多少个 "NG" 辅音单位（$0 \le x \le \min(N, G)$）。
• $y$：将多少个 Y 用作元音（$0 \le y \le Y$），则用作辅音的 Y 个数为 $Y - y$。

3. 可用资源计算

对于一组固定的 $(x, y)$：

• 元音总数：

  $$v = V_0 + y$$

• 辅音“位置”总数（每个位置对应一个辅音，但 "NG" 占两个字母却只算一个位置）：
  包括：

  • 普通辅音 $C_0$ 个（每位置 1 字母）
  • 用作辅音的 $Y$：$Y - y$ 个（每位置 1 字母）
  • 剩余的单独 N 和 G：$(N - x) + (G - x) = N + G - 2x$ 个（每位置 1 字母）
  • 使用的 "NG" 单位：$x$ 个（每位置 2 字母）

  因此辅音位置总数：

  $$c = C_0 + (Y - y) + (N + G - 2x) + x = C_0 + Y - y + N + G - x $$

• 可用 "NG" 单位数：$x$。

4. 最大音节数

每个音节需要 $1$ 个元音和 $2$ 个辅音位置，因此最大可能的音节数（不考虑 "NG" 带来的长度优势）为：

$$s_{\max} = \min\left(v,\ \left\lfloor \frac{c}{2} \right\rfloor\right) $$

实际构造时，只需取出 $s$ 个元音和 $2s$ 个辅音位置即可。为了最大化总字母数，应尽可能多用 "NG" 单位（因为每个 "NG" 贡献 2 字母，而普通辅音只贡献 1 字母）。在 $2s$ 个辅音位置中，最多能使用 $\min(x, 2s)$ 个 "NG" 单位。

5. 单词长度计算

每个音节的基础长度是 $3$（两个单字母辅音 + 一个元音），每将一个普通辅音替换为 "NG" 会额外增加 $1$ 个字母。因此总长度为：

$$\text{len} = 3s + \min(x, 2s)$$

其中 $s$ 取 $s_{\max}$ 时能得到最大长度。可以证明，取 $s = s_{\max}$ 一定优于任何更小的 $s$（因为减少音节数会同时减少 $3s$ 项，而 $\min(x,2s)$ 最多线性增长，不可能弥补损失），因此只需计算 $s_{\max}$ 对应的长度即可。

6. 算法步骤

1. 统计 $V_0, C_0, Y, N, G$。
2. 初始化答案 $\text{ans} = 0$。
3. 枚举 $x = 0 \dots \min(N, G)$：
   • 枚举 $y = 0 \dots Y$：
     • $v = V_0 + y$
     • $c = C_0 + Y - y + N + G - x$
     • $s = \min(v,\ \lfloor c/2 \rfloor)$
     • $\text{len} = 3s + \min(x, 2s)$
     • 更新 $\text{ans} = \max(\text{ans}, \text{len})$
4. 输出 $\text{ans}$。

7. 复杂度分析

枚举 $x$ 最多 $O(|S|)$ 种，$y$ 最多 $O(|S|)$ 种，总复杂度 $O(|S|^2)$。由于 $|S| \le 5000$，$|S|^2 = 2.5 \times 10^7$，在时限内可行。实际实现时可以剪枝优化，但按题目给定的标程思路已足够。

8. 样例验证

以样例 1 "ICPCJAKARTA" 为例：

• $V_0 = 4$（A×3, I×1），$C_0 = 7$，$Y=0$，$N=0$，$G=0$。
• 唯一组合 $x=0,y=0$：$v=4$, $c=7$, $s=\min(4,3)=3$, $\text{len}=3\times3+0=9$，输出 9，正确。

其它样例均可通过手动验证。

参考代码（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int V0 = 0, C0 = 0, Ycnt = 0, Ncnt = 0, Gcnt = 0;
    for (char ch : s) {
        if (ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U')
            V0++;
        else if (ch == 'Y')
            Ycnt++;
        else if (ch == 'N')
            Ncnt++;
        else if (ch == 'G')
            Gcnt++;
        else
            C0++;
    }
    int ans = 0;
    for (int x = 0; x <= min(Ncnt, Gcnt); x++) {
        for (int y = 0; y <= Ycnt; y++) {
            int v = V0 + y;
            int c = C0 + (Ycnt - y) + (Ncnt + Gcnt - x);
            int s = min(v, c / 2);
            int len = 3 * s + min(x, 2 * s);
            ans = max(ans, len);
        }
    }
    cout << ans << endl;
    return 0;
}