题面

数据范围

≤

1\leq n\leq5\times10^5

1≤n≤5×105 。

题解

≤

n\leq 20

n≤20 的状压应该都会吧，状态记录已经选了的蛋糕集合，以及蛋糕序列的尾部奶油，然后枚举蛋糕转移。

总共有

10 种不同的蛋糕，数据很小。

把最后的蛋糕塔等效为一个序列，如果有连续三个同种蛋糕，美味度分别为

A,B,C

A,B,C，那么就可以把他们等效为一个美味度为

A+B+C

A+B+C 的同种蛋糕，放在原来的位置。于是连续的一段奇数个同种蛋糕都可以合并成一个蛋糕。

现在我们证明一个结论：存在最优解，满足对于每种蛋糕，按上述方式合并后，蛋糕数量不超过 2 个（至多两段连续奇数段）。

考虑用调整法，对于任意解中的任意一种蛋糕，合并后仍存在三个不同位置的蛋糕

a,b,c

a,b,c ，已知每种蛋糕都有两种方向，由鸽笼原理可得，这三块蛋糕一定至少有两块蛋糕是同向的。不妨设

a,b

a,b 的奶油都是左

X 右

Y ，

a<b

a<b ，那么区间

[

−

]

[a+1,b-1]

[a+1,b−1] 的整体就是左

Y 右

X 。我们把

[

−

]

[a+1,b-1]

[a+1,b−1] 对称翻转，然后移开

a,b

a,b ，把

a,b

a,b 拼起来塞到

c 的一侧，最后合并

a,b,c

a,b,c 。整个过程结束，蛋糕序列美味度总和不变，仍然合法，

a,b,c

a,b,c 却变成了一块蛋糕。

既然合并后每种蛋糕可以不超过两个，那么我们就可以提前把每种蛋糕最大的前奇数个合并到一起，最多留下一个最小的，这样每种蛋糕一开始就只有两个，总的蛋糕数量

n 降至

20 ，

就可以用状压了。

CODE

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<random>

#include<vector>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 500005

#define LL long long

#define ULL unsigned long long

#define DB double

#define lowbit(x) (-(x) & (x))

#define ENDL putchar('\n')

#define FI first

#define SE second

LL read() {

    LL f=1,x=0;int s = getchar();

    while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}

    while(s >= '0' && s <= '9') {x = (x<<3) + (x<<1) + (s^48); s = getchar();}

    return f*x;

}

void putpos(LL x) {if(!x)return ;putpos(x/10);putchar('0'+(x%10));}

void putnum(LL x) {

    if(!x) {putchar('0');return ;}

    if(x<0) {putchar('-');x = -x;}

    return putpos(x);

}

void AIput(LL x,int c) {putnum(x);putchar(c);}

int n,m,s,o,k;

const int id[4][4] = {{0,1,2,3},{1,4,5,6},{2,5,7,8},{3,6,8,9}};

priority_queue<LL> q[15];

int a[25];

LL w[25];

vector<int> bu[15];

int le[15];

LL dp[1<<20|5][4];

int main() {

	freopen("cake.in","r",stdin);

	freopen("cake.out","w",stdout);

	n = read();

	for(int i = 1;i <= n;i ++) {

		k = read();

		char A = ' ',B = ' ';

		while(A == ' ') A = getchar();

		while(B == ' ') B = getchar();

		int bl = id[A-'W'][B-'W'];

		q[bl].push(k);

	}

	for(int i = 0;i < 10;i ++) {

		while((int)q[i].size() > 2) {

			LL A = q[i].top();q[i].pop();

			LL B = q[i].top();q[i].pop();

			LL C = q[i].top();q[i].pop();

			q[i].push(A+B+C);

		}

		while(!q[i].empty()) {

			a[m] = i; w[m] = q[i].top(); q[i].pop();

			bu[i].push_back(m); le[i] ++;

			m ++;

		}

	}

	int tp = (1<<m);

	LL ans = 0;

	for(int i = 1;i < tp;i ++) {

		for(int j = 0;j < 4;j ++) {

			for(int k = 0;k < 4;k ++) {

				for(int s = 0;s < le[id[k][j]];s ++) {

					int x = bu[id[k][j]][s];

					if(i & (1<<x))

						dp[i][j] = max(dp[i][j],dp[i-(1<<x)][k] + w[x]);

				}

			}

			ans = max(ans,dp[i][j]);

		}

	}

	AIput(ans,'\n');

	return 0;

}