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>usingnamespace std;typedeflonglong ll;inline ll max(ll a,ll b){return a>b?a:b;}#define M 100005char 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;}