Cake TrialAI (CI翻译)
The cake is a lie.— Portal
GLaDOS, the artificial intelligence of the Aperture Science Enrichment Center, decided to conduct another test for Chell. This time, the test is about cakes.
GLaDOS arranged $n$ cakes in a row. Each cake can be either real (T) or fake (F). Chell must guess which cakes are real and which are fake. Chell has a unique ability: she can determine exactly whether a cake is real just by looking at it. However, in her answer, she must satisfy GLaDOS's strange condition: all fake cakes in Chell's answer must form one contiguous subsegment (possibly empty).
Initially, GLaDOS prepared some arrangement of cakes, but some cakes have not been placed yet. You are given a string $s$ of length $n$ describing the current situation:
$s_i =$T, if the$i$-th cake is real;$s_i =$F, if the$i$-th cake is fake;$s_i =$N, if there is no cake at the$i$-th position yet, and GLaDOS may still place either a real or a fake cake there at her discretion.
After GLaDOS finishes the arrangement (replaces all
N
with
T
or
F
), Chell will see the final arrangement and will know exactly for each cake whether it is real or fake. Chell will choose a contiguous segment $[l, r]$ ($1 \le l \le r \le n$) that she will declare to be the set of fake cakes (or she may declare all cakes to be real). All cakes outside this segment are considered real. Chell wants her answer to be as close to the truth as possible, so she will choose the segment to minimize the number of mistakes.
GLaDOS, being cunning, wants to make Chell's life harder. She wants to place the remaining cakes (replace all N with T or F) so that the number of mistakes Chell is forced to make, under her optimal choice of segment, is as large as possible.
Help GLaDOS determine the maximum number of mistakes she can guarantee.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
The first line of each test case contains one integer $n$ ($1 \le n \le 500$) — the number of cakes.
The second line of each test case contains a string $s$ of length $n$ consisting of the characters T, F, or N — the current arrangement of cakes.
It is guaranteed that the sum of $n^3$ over all test cases does not exceed $500^3$.
Output
For each test case, output one integer — the maximum number of mistakes that GLaDOS can guarantee.
Note
In the first test case, $s =$ FTFF, all cakes are already placed. Chell will choose the segment $[3, 4]$, resulting in the answer TTFF, and she will have $1$ error.
In the second test case, $s =$ TNFTT, $1$ cake is not placed. For any replacement of N with T or F, the fake cakes form a continuous segment that Chell can choose, so the answer is $0$.
In the third test case, $s =$ TFTTTN, GLaDOS will replace N with F, obtaining TFTTTF. It can be shown that the answer is at least $1$. If Chell chooses the segment $[2, 2]$, i.e., gives the answer TFTTTT, she will make exactly $1$ error.
In the fourth test case, $s =$ TNNFTF, GLaDOS will arrange the cakes as follows: TFTFTF. Chell will choose the segment $[2, 4]$ (answer: TFFFTT), making $2$ errors.
{"titleZh":"蛋糕试炼","bodyZh":"<题目描述>\n蛋糕是个谎言。——《传送门》\n\nAperture Science Enrichment Center 的人工智能 GLaDOS 决定为 Chell 进行又一次测试。这一次，测试内容与蛋糕有关。\n\nGLaDOS 将 $n$ 个蛋糕排成一列。每个蛋糕可以是真的（T），也可以是假的（F）。Chell 必须猜测哪些蛋糕是真的、哪些是假的。Chell 拥有一种特殊能力：只要看一眼，她就能准确判断一个蛋糕是真是假。然而，在作答时，她必须满足 GLaDOS 奇怪的要求：Chell 答案中的所有假蛋糕必须构成一个连续子段（也可以为空）。\n\n最初，GLaDOS 准备了某种蛋糕排列，但其中一些蛋糕尚未放置。给定一个长度为 $n$ 的字符串 $s$，描述当前情况：\n\n- $s_i =$ T，表示第 $i$ 个蛋糕是真的；\n- $s_i =$ F，表示第 $i$ 个蛋糕是假的；\n- $s_i =$ N，表示第 $i$ 个位置还没有蛋糕，GLaDOS 仍可以自行决定在那里放置真蛋糕或假蛋糕。\n\nGLaDOS 完成排列后（将所有 N 替换为 T 或 F），Chell 会看到最终的排列，并准确知道每个蛋糕是真是假。Chell 将选择一个连续子段 $[l, r]$（$1 \le l \le r \le n$），并宣称该子段中的蛋糕是假的（她也可以宣称所有蛋糕都是真的）。子段之外的所有蛋糕都被认为是真的。Chell 希望自己的答案尽可能接近事实，因此她会选择一个子段，使错误的蛋糕数量最少。\n\n狡猾的 GLaDOS 想让 Chell 更加难受。她希望放置剩余的蛋糕（将所有 N 替换为 T 或 F），使得在 Chell 选择最优子段的情况下，她不得不犯的错误数量尽可能多。\n\n请帮助 GLaDOS 求出她能够保证的最大错误数量。\n\n## 输入格式\n\n每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。\n\n每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 500$）——蛋糕的数量。\n\n每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 T、F 和 N 构成——当前的蛋糕排列。\n\n保证所有测试用例的 $n^3$ 之和不超过 $500^3$。\n\n## 输出格式\n\n对于每个测试用例，输出一个整数——GLaDOS 能够保证的最大错误数量。\n\n## 说明\n\n在第一个测试用例中，$s =$ FTFF，所有蛋糕都已经放置。Chell 会选择子段 $[3, 4]$，得到答案 TTFF，并犯下 $1$ 个错误。\n\n在第二个测试用例中，$s =$ TNFTT，有 $1$ 个蛋糕尚未放置。无论将 N 替换为 T 还是 F，假蛋糕都会构成一个连续子段，Chell 都可以选择该子段，因此错误数量为 $0$。\n\n在第三个测试用例中，$s =$ TFTTTN，GLaDOS 会将 N 替换为 F，得到 TFTTTF。可以证明，错误数量至少为 $1$。如果 Chell 选择子段 $[2, 2]$，即给出答案 TFTTTT，她恰好会犯下 $1$ 个错误。\n\n在第四个测试用例中，$s =$ TNNFTF，GLaDOS 会按如下方式排列蛋糕：TFTFTF。Chell 会选择子段 $[2, 4]$（答案为 TFFFTT），并犯下 $2$ 个错误。"}AI (CI翻译)
样例
10
4
FTFF
5
TNFTT
6
TFTTTN
6
TNNFTF
7
TNFNTNF
6
NNFFNN
7
TNTFNTN
1
N
5
NNNNN
10
NNNTTNNNFN
1
0
1
2
2
2
2
0
2
3
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。