cf353D. Queue（整体考虑转移）

D. Queue
f[i]表示第i个F需要多少时间才能让所有的M都移到她后面，那么我们考虑转移，分为两种情况。
第i个F和第i-1个F挨着，那么显然f[i]=f[i-1]+1
假如中间隔着一些M，
可以分为两种情况，假如i可以在i-1完成之前追上它，那么就是f[i-1]+1，否则就说明
i一直在进行交换，时间为在i之前的M的个数，而我们应当取两者中较大的。
所以f[i]=max(f[i-1]+1, m)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const ll cost=1e12+1;
const int N=1e6+5;
const int mo=998244353;
char s[N];
int f[N],a[N],n,tot,m;

int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	
	scanf("%s",s+1);
	n=strlen(s+1);
	
	int st=1;
	while (s[st]=='F' && st<=n) st++;
	
	fo(i,st,n) {
		if (s[i]=='M') m++;
		else {
			++tot;
			f[tot]=max(f[tot-1]+1, m);
		}
	}
//	fo(i,1,tot) printf("%d ",f[i]);
//	return 0;
	
	printf("%d",f[tot]);
	
	return 0;
}