CF353D

2022-07-25 题解

题目大意：给出一个仅由字母F和M组成的字符串。每次操作可以把串中所有为"MF"的子串变成"FM"，问多少次操作可以使所有的M都位于F后面。

照此规则进行操作，要使每个F的前面都不再有M，就要让所有F与原先在它之前所有的M都交换一次位置。

看起来只要统计各个F之前M的数量，取个最大值就是答案，但事实显然不是这样，因为并不能保证每次操作中每个F都能与它前面的M进行交换，——在某些操作中，可能存在这样的F，它的前一个紧邻元素还是F，但它再前面的元素却存在M。

这时候考虑另一条性质：原串中出现的第x个F之前出现过M，对于出现的第x个F和第x+1个F（不一定紧邻），第x+1个F所需要的操作次数不会少于第x个F的操作次数加上1，——因为需要把前面的M全部传到后面。由此就能写出代码了

#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1000005];
char s[1000005];
signed main()
{
    int n, i, summ = 0, res = 0;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (i = 1; i <= n; i++)
    {
        if (s[i] == 'F')
        {
            if (summ)
                dp[i] = max(dp[i - 1] + 1, summ);

            res = max(res, dp[i]);
        }
        else
        {
            summ++;
            dp[i] = dp[i - 1];
        }
    }
    printf("%lld", res);
    return 0;
}