TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2974
  • 题目
  • P2974射箭
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    问题描述

       何老板是一名箭术爱好者,今天他又到箭馆里去玩射箭游戏。
       游戏中会出现m(编号1到m)只怪兽,怪兽按编号1到m依次出现。每个怪兽的颜色和价值可能不同。若当前出现的是一只颜色为x的怪兽,何老板须用一只颜色同为x的箭才能杀死这只怪兽。
       游戏中,何老板有n(编号1到n)只箭,每只箭的颜色可能不同。游戏规定必须从第1号箭开始,用一段连续编号的箭去射杀连续一段怪兽,若遇到某只怪兽无法被杀死,游戏结束(当然,箭用完了或者没有怪兽可杀了,游戏也会结束)。
       也就是说,一开始只能射1号箭。若选1号箭射y号怪兽,那么只能用2号箭射y+1号怪兽,3号箭射y+2号怪兽......,若第k号箭无法杀死第y+k-1号怪兽,游戏结束,该局游戏得分为k-1。
       每秒钟会有一只怪兽出现在屏幕上,一秒钟以后该怪兽会消失,不会再出现了。何老板一秒钟可以射出一支箭,且百发百中,现在已知每个怪兽的颜色和价值,问何老板最多能得多少分。输出最高得分的方案和该方案杀死的怪兽的总价值,若有多种方案,输出总价值最大的那种(在得分最高的前提下,要求总价最高)。

    输入格式

    第一行,两个整数n和m,1<=n<=m<=20000
    第二行,n个大写字母,表示编号1到n的箭的颜色。
    第三行,m个大写字母,表示编号1到m的怪兽的颜色。
    第四喊,m个空格间隔的整数,表示编号1到m的怪兽的价值。

    输出格式

    一行,两个空格间隔的整数,分别表示最大得分和最大总价值。

    样例输入 1

    4 8
    ABCD
    ABCEDABC
    1 6 3 5 1 4 2 9 

    样例输出 1

    3 15

    样例输入 2

    7 15
    ZPFHOOX
    ZPFZPFHOOZPFHOO
    729 221 256 196 557 234 232 460 546 645 107 972 421 783 246 

    样例输出 2

    6 3174

    样例输入 3

    10 22
    TEBZLVRQDN
    TEBZLVTEBZLVRQTEBZLVRQ
    275 276 305 467 698 612 599 429 500 996 843 61 651 335 860 565 544 968 919 90 718 136 

    样例输出 3

    8 4800

    提示

    数据范围:
    50% 1<=n<=m<=200
    100% 1<=n<=m<=20000
    0<=怪兽的价值<=1000

    样例1说明:
    用编号1、2、3这连续三只箭射杀1、2、3号或者6、7、8号怪兽
    杀死6、7、8三只,价值为4+2+9