C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 8672K, 提交时间: 2019-10-08 21:44:01

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

int dp[101][51][201][2];
string s;
int ans;
int n;

inline void dfs(int i,int fz,int pos,int dec)
{
	if(i==s.size())
	{
		if(fz==0) ans=max(ans,abs(pos));
		return ;
	}
	if(fz<0||dp[i][fz][pos+100][dec]) return ;
	dp[i][fz][pos+100][dec]=1;
	if(s[i]=='F')
	{
		dfs(i+1,fz-1,pos,-1*dec);
		dfs(i+1,fz,pos+dec,dec);
	}
	else if(s[i]=='T')
	{
		dfs(i+1,fz-1,pos+dec,dec);
		dfs(i+1,fz,pos,dec*-1);
	}
}
int main()
{
	cin>>s;
	cin>>n;
	memset(dp,0,sizeof(dp));
	ans=0;
	dfs(0,n,0,1);
	cout<<ans<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 88ms, 内存消耗: 10856K, 提交时间: 2018-03-16 19:35:17

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

int n,m,ans;
char c[105];
map <pair <int,int> ,bool> M[105][55];

void dfs(int i,int j,int x,int d)
{
	if (j<0)  return;
	if (M[i][j][mp(x,d)])  return;
	M[i][j][mp(x,d)]=1;
	if (i>m)  {if (~j&1)  ans=max(ans,abs(x));  return;}
	if (c[i]=='T')  dfs(i+1,j,x,-d),dfs(i+1,j-1,x+d,d);
	else  dfs(i+1,j,x+d,d),dfs(i+1,j-1,x,-d);
}

void work()
{
	scanf("%s\n%d",c+1,&n),m=strlen(c+1);
	dfs(1,n,0,1);	
	printf("%d",ans);
}

int main()
{
	work();
	return 0;
}