记忆化搜索
就是暴力，多一步优化，走过的路别走了。说实话，可能是数据水了，居然能过。
const int N = 510;
string s;
int n, ans;
bool st[501][501][2][50];
void dfs(int x, int idx, int dir, int k)
{
if (st[x][idx][dir][k]) return;
st[x][idx][dir][k] = 1; //走过的路不走了
if (x == s.size())
{
if (k % 2 == 0) ans = max(ans, abs(idx));
else ans = max(ans, abs(abs(idx) - 1));
return;
}
if (s[x] == 'F')
{
if (k > 0) dfs(x + 1, idx, dir ^ 1, k - 1);
if (dir == 0) dfs(x + 1, idx + 1, dir, k);
else dfs(x + 1, idx - 1, dir, k);
}
else
{
if (k > 0)
{
if (dir == 0) dfs(x + 1, idx + 1, dir, k - 1);
else dfs(x + 1, idx - 1, dir, k - 1);
}
dfs(x + 1, idx, dir ^ 1, k);
}
}
void solve()
{
cin >> s >> n;
dfs(0, 0, 0, n);
cout << ans << '\n';
}