记忆化搜索

就是暴力，多一步优化，走过的路别走了。说实话，可能是数据水了，居然能过。

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';
}