F 礼物(2) /[模板]FFT字符串匹配

F 礼物(2) /[模板]FFT字符串匹配

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

F 礼物(2)

时间限制:1s
空间限制:64MB

题目背景

请注意:本题可能具有较高的难度。
pzr的同学就要过生日了,pzr打算送给她一对手环。
每只手环是由红(R)、绿(G)、蓝(B)三种颜色的珠子串成的。

题目描述

给定两只手环上珠子的颜色。pzr认为,这两只手环之间有一定的匹配度w。
我们这样定义匹配度w:首先,每两种颜色之间都有一定的匹配度,例如红色和红色有100的匹配度,而红色和绿色有10的匹配度。
而一对手环的匹配度w则是对应位置的匹配度之和,因为手环可以旋转,所以pzr可以最大化这个值。
你可以结合样例来理解这段话。
求:手环的最大匹配度。

输入格式

前三行每行三个整数\(a_{ij}\)用空格隔开,含义如下图所示,如第二行第三列就表示绿色和蓝色的匹配度。
保证\(a_{ij}=a_{ji}\)

R G B
R
G
B

接下来两行,每行一个由"R"、"G"和"B"构成的字符串
保证两个字符串等长。

输出格式

一个整数,表示最大匹配度。

数据范围及限制

\(1\le L \le 200206,L\)是字符串的长度。
两种颜色的匹配度\(0\le a_{ij}\le 20\)

样例输入1

10 1 1
1 10 1
1 1 10
RGB
BRG

样例输出1

30

样例1解释

有三种计算的方式:
不进行旋转,RGB和BRG匹配,值为1+1+1=3
旋转错开一位,RGB和GBR匹配,值为1+1+1=3
旋转错开两位,RGB和RGB匹配,值为10+10+10=30
pzr会选择最后一种。

样例输入2

20 10 1
10 20 10
1 10 20
RBGR
GRBB

样例输出2

61

样例2解释

有四种计算的方式:
22 22 61 60
不进行旋转,RBGR和GRBB匹配,值为10+1+10+1=22
旋转错开一位,RBGR和BGRB匹配,值为1+10+10+1=22
旋转错开两位,RBGR和BBGR匹配,值为1+20+20+20=61
旋转错开三位,RBGR和RBBG匹配,值为20+20+10+10=60
pzr会选择第三种。答案是61。

样例输入3

0 1 1
1 10 20
1 20 5
RBGRR
GRBBR

样例输出3

26

样例3解释

五种方案:23 23 13 8 26

娱乐赛(2)

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2021-04-18 08:00
结束于
2021-04-25 08:00
持续时间
168.0 小时
主持人
参赛人数
34