dh 收到了学妹给他发的一个只包含前五个小写字母的字符串 S,(既只包含 a,b,c,d,e 五种字符)虽然他也不知道是啥意思,但是他还是拿着 S 去跟 Bear2 装 B 去了,终于他把 Bear2 惹急了。
Bear2 就想把他的最爱的给毁掉,但是 dh 给他的手机加了密, Bear2 要删除任意一个字母都会付出一定的代价,而这个代价与这个字母左右两个相邻的字母有关。第 i 个字母会保护第 j 个字母,其能力值为 W i,j。
第1个字母为 a, W1,2表示字母 a 保护 字母 b 的能力值为 W 1,2。
设删除要第 i 位的字符 c 的代价为 W l,c+ W r,c( l,r 分别表示离第 i 位左右两边相邻还没被删除的字符),如果第 i 位左边为空则 W l,i为零,右边同理。
您能帮 Bear2 求出最小的代价吗?
输入格式:
第一行给出样例组数 t(1<=t<=10)
每组样例的第 1 行到第 5 行,每行给出 5 个的非负整数。
第 i 行,第 j 列的非负整数 W i,j(0<=W i,j<=500) 表示第 i 个字母保护 第j 个字母的能力值 。
第 6 行给出一个正整数 n(1<=n<=200) 表示字符串 S 的长度
第 7 行给出字符串 S
输出格式:
在一行中输出最小的代价
输入样例:
在这里给出一组输入。例如:
1
32 40 17 40 35
13 19 7 3 5
11 41 42 6 17
47 21 42 35 23
20 45 36 16 42
5
addbd
输出样例:
在这里给出相应的输出。例如:88
提示:
40%的数据n<=20
100%的数据n<=200
![](https://profile-avatar.csdnimg.cn/default.jpg!4)
这道算法题怎么解,写出代码,语言不限
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- 专家-皆知 2024-05-14 21:11关注
遍历所有可能的子串,计数每种字符出现次数。
以上回复有部分引自免费微信小程序:皆我百晓生。 如问题尚未解决,还请稍待,如有疑问请回复进一步沟通。
解决 无用评论 打赏 举报
悬赏问题
- ¥15 数据库原理及应用上机练习题
- ¥30 征集Python提取PDF文字属性的代码
- ¥15 如何联系真正的开发者而非公司
- ¥15 有偿求苍穹外卖环境配置
- ¥15 代码在keil5里变成了这样怎么办啊,文件图像也变了,
- ¥20 Ue4.26打包win64bit报错,如何解决?(语言-c++)
- ¥15 clousx6整点报时指令怎么写
- ¥30 远程帮我安装软件及库文件
- ¥15 关于#自动化#的问题:如何通过电脑控制多相机同步拍照或摄影(相机或者摄影模组数量大于60),并将所有采集的照片或视频以一定编码规则存放至规定电脑文件夹内
- ¥20 深信服vpn-2050这台设备如何配置才能成功联网?