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