CF353D

这题是我在模拟赛中做的。
我觉得大部分人都会以为这是到逆序对的题目吧，（好吧，我也以为是求逆序对）。但是，仔细一看，你可以发现这不是逆序对。为什么呢？注意到题目：“每秒如果一个女生前边有一个男生，两个人就可以进行调换位子”，也就是说，就算是在同一秒中，也还是可以换。（不过一个人只能一秒内只能换一次，不然直接输出1不就得了（滑稽））；
可是由于女生不会和女生换（因为都是女的），所以当女生堵在一起的时候，就得重新算过了。
我觉得吧，这题也就那么点难度（也不知道是不是div 3的D，反正div 2不会那么水（古老的题解……））。
接下来附上我这像贪心的动归（或者说是像动归的贪心）。

#include<bits/stdc++.h>
using namespace std;
int a[1000001]={0};
int main()
{
//  freopen("queue.in","r",stdin);
//  freopen("queue.out","w",stdout);//当时模拟赛的时候要用freopen的，不要注意这种细节
    string s;
    cin>>s;
    int last=-1,count=-1;//初始化为-1
    int l=s.size();
    for(int i=0;i<l;i++)
    {
        if(s[i]=='M')continue;//根据女生的，如果这里是男的话就不要动了，只要让女的动就可以了
        count++;
        if(last==-1){last=i;a[i]=i-count;continue;}
        if(a[last]==0){last=i;a[i]=i-count;continue;}
        a[i]=max(i-count,a[last]+1);
        last=i;
    }
    cout<<a[last]<<endl;
    return 0;
}