fjwc2019 D3T2 送分题

#185. 「2019冬令营提高组」送分题

这是原题….. P3615 如厕计划

手推一推你发现，显然男性不能多于女性。

然后你或许可以发现一个神奇的性质。

对于每个序列，我们记$M$为$1$，$F$为$-1$

蓝后我们统计这个序列的后缀和。

如果这个序列合法，那么每个后缀和都$<=1$

如果出现$>=2$的……

举个栗子

F　　F　　F　　M　　M　　M　　M　　M　　F　　F

0　　1 　　2　　3 　   2　　  1　　 0　　-1　　-2　　-1

这个数列显然是不合法的。

我们要让它合法，就要把若干个M向左移。

你希望使得所有人中最大的不满值尽可能小，那么我们就把M都移到队首去（不管左移几位不满值都不变），并优先把靠右的M移走，这显然是最优的。

后缀和最大为3，那么我们只需移动2个M到队首

M　　M　　F　　F　　F　　M　　M　　M　　F　　F　

0　　-1 　　-2　　-1 　  0　   1　　 0　　-1　　-2　　-1

这个数列就合法了。

队列以复读的形式给出，如何处理？

我们发现（感性理解吧……），对于相同的$k$段，统计一段的后缀和，与F的个数 – M的个数。

最后一段需要把后缀和最大值个的M移到队首，而前面的$k-1$段就只需要把max（F的个数 – M的个数）的M移走即可。

通过这个方法得出的数列一定满足每次匹配都是’MF’的情况（M消耗完后则为’FF’）

但是我们允许’FM’的状况出现。

所以我们可以少移一次。

那么答案需-1

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
inline ll max(ll a,ll b){return a>b?a:b;}
#define M 100005
char a[M<<];
ll n,m,b[M],p[M],d[M],ans,tot;
int main(){
    freopen("queue.in","r",stdin);
    freopen("queue.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=;i<=m;++i){
        scanf("%s%lld",a,&b[i]);
        for(int j=strlen(a)-;j>=;--j){
            p[i]+=(a[j]=='M'?:-);
            d[i]=max(d[i],p[i]);
        }tot+=p[i]*b[i];
    }
    if(tot>){
        puts("-1"); return ;
    }tot=;
    for(int i=m;i;--i){
        ans=max(ans,tot+(b[i]-)*max(,p[i])+d[i]);
        tot+=p[i]*b[i];
    }
    printf("%lld",ans?ans-:);
    return ;
}