题意描述

我走在每天必须面对的分岔路
我怀念过去单纯美好的小幸福
爱总是让人哭
让人觉得不满足
天空很大却看不清楚
好孤独
天黑的时候
我又想起那首歌
突然期待下起安静的雨
原来外婆的道理早就唱给我听
下起雨
也要勇敢前行
我相信
一切都会平息
我现在好想回家去
天黑黑
欲落雨
天黑黑
黑黑

当整个世界陷入黑暗的时候，身为光明之神的Zyh想要用自己的若干个能量源和若干个集流器将这些能量源并成一个最大的能量源，这样他就可以造出最大的灯来照亮整个世界。

具体地来说每个能量源可以直接给出$e_i$的能量。

而每个集流器是由两个接受端口和一个输出端口组成的。集流器有两种：$A$类和$B$类。

其中，$A$类是叠加集流器，可以将两个接收端口的能量叠加并输出。$B$类是取代集流器，可以将两个接受端口的能量较大那个输出。

现在有$n-1$个集流器，$n$个能量源。Zyh给出了集流器的连接方式。

他想知道怎样放置能量源，能够使最后的输出最大化。

输入格式

第一行是一个字符串，表示连接的方式。

给出的形式如下：$X$表示一个单独的输出能量源的放置处；$A,S_1,S_2$，其中$S_1$和$S_2$表示两个输出能量.

$A$表示使用叠加集流器将能量并成一个，然后这本身也成为一个新的输出能源；

$B$也是同理，只不过是使用取代集流器。并且保证$A$和$B$的个数为$n-1$个。$X$的个数为$n$个。

第二行是$n$个正整数，表示这几个能量源可以提供的能量大小。

输出格式

输出仅有一个数，表示最大的输出能源。

Input & Output ‘s examples

Input ‘s eg 1

BXBXX
8 2 3

Output ‘s eg 1

Input ‘s eg 2

AXBXX
8 2 3

Output ‘s eg 2

数据范围与约定

对于$20\%$的数据，保证$0<n<10$

对于$60\%$的数据，保证$0<n<3 \times 10^3$

对于$100\%$的数据，保证$0< n <2\times 10^5$ $0 < e_i< 10^4$

分析

一道巧妙的贪心题。

手绘一下两个样例，不难发现，$A$型集流器对于能量没有损失，而$B$型集流器会损失掉较小的能量。

因此，我们可以考虑每一次都损失掉能量值最小的能量球。

之后呐？

或许您会将$B$型能量球的数量记为$b$，然后将损失掉前$b$个能量球？

~~然后您就成功的得到了60分~~

为什么这样是错的呐？我们考虑举反例。

若在一个$B$型集流器后接上两个$A$型集流器，就像下图

则我们失去的不是一个能量球，而是两个。

对于这个反例，我们直接在输入时使用栈模拟处理即可。

具体实现方法和剩下的细节见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 200001

using namespace std;

ll n , m , a[N];
string s;
ll x;
ll ans = 0;

stack<int > S;

bool cmp(ll a , ll b){
    return a > b;
}

int main(){
    cin >> s;
    for(int i = 0; i < s.length(); i ++){
        if(s[i] == 'X'){
            x ++;       //统计能量球的数量
        }
    }
    for(int i = 1; i <= x; i ++){
        scanf("%lld" , &a[i]);
    }
    sort(a + 1 , a + 1 + x , cmp);  //对能量球进行降序排序
    for(int i = s.length() - 1; i >= 0; i --){  //倒序扫描，便于模拟
        if(s[i] == 'X'){    //如果当前位置可以放能量球，则放入
            S.push(1);
        }
        else if(s[i] == 'A'){   //如果是A型集流器，则将后边的两个位置加起来
            int top1 = S.top();
            S.pop();
            int top2 = S.top();
            S.pop();
            S.push(top1 + top2);
        }
        else{       //如果是B型，则删掉较小的那一个。
            int top1 = S.top();
            S.pop();
            int top2 = S.top();
            S.pop();
            if(top1 > top2){
                S.push(top1);
            }
            else{
                S.push(top2);
            }
        }
    }       //最后的栈顶则是可以取到的能量球数。
    for(int i = 1; i <= S.top(); i ++){
        ans += a[i];
    }
    printf("%lld" , ans);
    return 0;
}