POJ3280(DP)

时间:2023-03-08 18:24:56

题目大意是说一个字符串,每插入或者删除一个字符都需要一定的代价,问怎样可以使这个字符串变成一个回文串,且花费最小。

首先明确的就是如果已经将区间[i,j]整理成为一个回文串(不管中间有多少个字符或者是以什么字符开头或者结尾),当DP到区间[i,j+1]时,我们可以在i-1的位置添加一个str[j+1]字符,或者将在j+1处的字符删除,得到一个新的回文串,而且我们这两步操作都没有借助或者影响区间[i,j]的情况。

因此,那我们就可以将添加或者删除整合在一起,对字符str[j+1]的操作就按照添加和删除中花费最小的一个计算。写出状态转移方程:

DP[j][i] = MIN(DP[j+1][i]+cost[str[j]-'a'], DP[j][i-1]+cost[str[i]-'a']);
          if(str[i] == str[j])DP[j][i] = MIN(DP[j][i],DP[j+1][i-1]);

这里的j是按照i-1到0枚举的,由于可能str[i] == str[j],因此也可以不操作,再将  不操作  与  添加或删除区间头或尾  比较。

当然,其实最初的想法是扩展出来四个状态,就是首删除,首添加,尾删除,尾添加,由此扩展开来求一个最小值

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABTUAAABHCAIAAABZOTSvAAAgAElEQVR4nO1dy3IcyXXtz4EwUvBXYAuS7AWX/ANDoQc2Dq3wAQNJIUuwIxQKrya4EMzwwsZIDseEd8MILgbdDfABdDVADknwIQ7QQFd6Ua/MmzezsrKrMru6T8VZkN1Vhdsn82bek4+bgwd7j4FOIYSIbgPgDSEESlBmI7oNALDOgA968wbqvKmLbkNPEYC6z0czIV8f3n3e5mtnX3+xstQBwBKidOVBdFNWHmhleg1EdYSN6DYAwDoDPujNG6jzpi66DT1Fx9RdPhf89fyrRV8OfQ4AUQB9HpTr6DYA3kBUR9iIbgMArDPgg968gTpv6qLb0FN0SZ1RnAshhPj0aLH3Q58DQBRAnwflOroNgDcQ1RE2otsAAOsM+KA3b6DOm7roNvQU3VEnLWuXpXgl2q9GTw33G9T7V5+E9Cyrz5WXXFz2lDoAWGZAnwflOroNgDcQ1RE2otsAAOsM+KA3b6DOm7roNvQUnVH39OsPBqX9xbsrur69vFm5lHskca5epT5nX7LoLH0M6gBgqQF9HpTr6DYA3kBUR9iIbgMArDPgg968gTpv6qLb0FN0Rl0xT+4wiV1Oehcz6rq2L2fdi08quZ7rc206PX+EzNL3gToAWGpAnwflOroNgDcQ1RE2otsAAOsM+KA3b6DOm7roNvQUXVH3xbsrV3lcqHE5rzt5vFDj8oz6owtZnxcvkYYDcsXeUrr4cNQBwHID+jwo19FtALyBqI6wEd0GAFhnwAe9eQN13tRFt6GniK/P+TuV6XfrVvPsQ0suuq6WuKPWAesJ6POgXEe3AfAGojrCRnQbAGCdAR/05g3UeVMX3Yaeomt9Xr++ndfnyqT6Yvq8qwTvqHXAegL6PCjX0W0AvIGojrAR3QYAWGfAB715A3Xe1EW3oafojDpzfri9y+eyGm93/rzjnO1BqAOApQb0eVCuo9sAeANRHWEjug0AsM6AD3rzBuq8qYtuQ0/RHXW156sVWrrV/eed7TYPSR0ALDOgz4NyHd0GwBuI6ggb0W0AgHUGfNCbN1DnTV10G3qKLqmzrDlXJsNbzd9evqR4BPnhAKBVdKzPy70xzNXheYkl6HIdoz1d7ZwhXAcrV18YB0fZhU9rBWNUZ67k6tGjvuCGtAnCl04fKvPqQJoh0a6A6wxVY0hlu3we3JI1R3MfVOJ40p4Us2RxKlVg3jptvmzemjnOV+45t5cLFt7y+hNwWrVf6LjHNEr0UOefdxh7dExdVBC2PdynQQL/Fl776MIs3GxyL3vVZfjFF71GSV14fd6tS2dw1udCiM6Dkj60MtDnRmR1hPnKWqlaaDShz9ceNRF/2N6OqWxZFV1pUbeEaO6DShDPb0MN0hVG563T5gv6PLqdS4gAPSateKayUDQhJ7ekG65GT9noQhnO63iyLQB1McCPlTSO4sLp86yPgD4Ph5K6KPq88zigmT5va8LTzHX4Am4I6HMjshrCfFVTqRbuuqDP1x51EX+3DZfBmLKyRcgYBDxYWJ8rjTyZxlnpojS25C2hXp/3tg+18AZ97k0dsI7UGdcpNHSijvS5hmJEZhF93rPhyOgoqetWn2sFY9zlIgWaNOyT40Jp9M7W25n0ubZmw8sxmnMdvbzr0Eifk/E/piCUSEWJ+ao/9Ki8Z7mDwsxG5iv7sSVFla4I/KpsxaqWTg3p1BZQcg1Ttef1udwBqAUqNbVaFhmpkbWovj5U5tWBcfylLGLWufhCtLotU5lpm6AYo3fJy+3Fq4TmPlg6++zqg1L0WZlefWCbYlnVm5odqVLl9aR6igvL1Eqo1hmuqWRf5ZmqKntVmDLiPZd4mfRfqSPIH7EGJ3ZPD1rl3PQ5nTNkV1Y//0rpEG0t2Id3n9NAkRku5KSF1RLlqexBtrIZXaMRdYAdK0ldWbsYySPVJabqEq3Etx5shr8m8Z7SRulT/XXTTg6H+Sn/lcwgqQobKouVQvkTA+tzrdo10Of6Zawrjvr8Ac1R2RXX0cu7Du76nN/vJBUfu3qnLCnm25BzgH7Fx5egqVKpVZqpvSSrqokN8zhreY8eBarLz4TDt0LIAXpdofBUAN3AvD5CC0bZMeyqA6tzW+jz/qC5D1bD4l+PZlK5Z0U8e36h6XOu8SnrhrFH/jCz6Wp+msU0WJnZ864+9XQT3ppT54lG+ly7smEUmVjm56tERduj56DP+canKr76nc+PzauCG+nzOkvMXWT1A62u0Yg6wI6VpI6fjtZ0kLs+t9RGn3gvpD6vN6y2BQiRziw8yp8Xaf5ca+zc9HleGNwQlAJ3fe6yinhxrqOXdx1c9bkWdliDeKk0tcShvVn0klnLfNVs/pxyW59SVR9HLFtkE9u0MhfvLFypaq9JTCO0UVVDwNeHyrw6qJ0/p5WHtquubttYn+89xvr2WGjug9KyNTllQFbozFImUxecN01am2aeRa8avfIerTXTO3qpqdRdwHtTT/buMGXUUJ/TFNnaLLrZc1VPD1/l6vU5tVBrN+pThVu6yyb63N0SvcckFdvgGo2oA+xYTerk8R1z19lInxfxHl2e7BPvaZFA/fp2GQ31uT5SSWbRtRbApCxWCmUpxdl/rg+duuhz62yPggb6vPtdHKIHrUxTfW6iiwrC6hHqmb3ZjJeZy3zltv/cwFiDI0nlB+3DJUyolL+EtNd6RlZz/KexEb1E1geuO1qLmqMvY8kqT53bQp/3Cc19UIrb8oL+9GhPSu9HZAkj+fI3kDFHbbbHPP/D9bNunQuNw7w3PGcvD1NGzfS5WR+agnKTp4evcs2Kg917xfR0pG2xdZcN17fbLOHuV0ea6lyjEXWAHatKHTutbThWw0Gfy/2veo9PvBdUn5uP9zO1AEZlsVIoa0UMfc7lp3Hcf26tBBWgzxuiVp/rk7pcadoO5MzeoHvmsiMzl/nKWsm1JeiWTT4ae0qUbNyq94DWc/MKQDobU5GvfQJ9vkSw63OHBaK0LlUXKV/o8/6guQ/K0U++pr1M5nI1ekpkoaXWqcM9tjlt0rDYM2WYZL/yKnUC06O/zl4epoya7j/nb9Aoqvf04FXOSZ+zZjdYRMk2NV77z22WsH2f8mGtazSiDrBjlanjHdkSmNn2n1evVT/0ifdC6nN9dVX1icG7raStDMrfFlaf611IdH2O9e17jxvoc1MXVe9Fqobsz6BXZj3zlVGfK+2FU6DGlkKb+pyMp2rtta2hpGxEL5H1gSkcpI2VQ0pYq9tCn/cJzX1QmQMsZPllKdTd9bl6g67PjYGgSzNYt5tDNtVn+VVmUJgyWlCf61lI6vV5pBy3zuvby/pjWqLfvT6vsWQhfY4dYa1jPajjU2Z2q88t8V5cfa5nzHFVFiuF8rcF2n9uTEaqN83GbWmd6HPkh1N5oE5odE6qTjMCa0P2FdTn9pmcJvq8pflzM7fQ5/2CJTujUnPcBxl5t7Wcegp9vnRo7oNKUTJnRqh9bu0G79b0ua01Y+y/Gj1d5DQvY0veAbrW54GTqlp4qysRfcVcMH1O/nStJe76vEG4GKzKrR5WkTpjp0n8SA/V6PKi9dTn6xFsiOIKlx9Oy1Xw+MFeZH1uyt3VOtfRy7sW/ABKOd7sMDr+/KvHDhIR+tzMg2H/ObPlxr7/3NySQp/3C1zlqSS6ez4OBvWD8dDnS4rmPqgWpTxGQz6xjAxK8NDnTfafM+KnaKZmi2xGM7bkHaArfR7q0GOdOtNXrvpcX7naQJ9zvRLtH531udkSpgMlOVmbj48Eq3Krh1WkzpAgWUv9667PLfuFV0if9084LAJRXCHzt9PU1vKdzKFTHehz09XpaHQ/WhnLwjmhr7ox7jzUcvyQLrB/bpaZz3y1kD5vlL/d2CKb8rdr3kTyw0Gf9wP2KJ87tpDWBHUc3bJh2BSqWvR5/3x5NdDcB0nhaqswTKm2tCSXponuen3eIH87NzmpdE+eGw6zh8OUUVf6vM7Tw1c544FkeX2jBjMzAU2SBNO4Qhg7O+3cnwaWMOEo9R3eNRpRB9ixktTV5Hw1ZcXWs7XrOc+N+dsX0ufN1ox0pc9rlcVKoawOYc9Xs0WWtTW1M30e7+zQpYK5o+XSmRo5ZAu0xzF99gOYrxbT5wucf+6Slol/J/R5v1A7uFNz/rk+U0QuZq+m8SU1lQ2z6KHQ3AcNcxGWVMBs42PukR30ufv552wgqOsxH96aU+eJzvR5raeHrnJ1+tzckTXR50x3WSym4A7iJZc5u63GnvZzirPodQ0vX+Y6KRaucrVHuAXGowtHn+2w1vUaTpG2WbPUnn++ULxnTlHpVAk70+d1ymKlUP68wOefs0vK5djx06Mu88NFKV3Ro1ZG73uYjof6iT5yrDZAsktDn1sIV9s+KWqR+FTew75cDVOUr6DP+wWXwR1mRTrvubVuK98w+/qL2vxw6l/sj0f3Hc19sLZL5bYqqJ2mZV36A0d9rnzOVFF7U6kf4ebBW7Dmq0N9LpcX7+ntw8JbvT5Xu6TnX2lJ/pz0+WNtcaUlIVz+NssiYd4S8hJ5/p892o0UX0PqGtalZdDnGefQ5wtDi7QtuavzSm7e6kJrdfGGdvT5njH+ZNChPieWLIlHdILyF3ajzwGV6+g2AN7I/CS6GUsCUAEAcbGePthsG6SBt/WkbnEsJW/+J+01AXPwcmDqlkefm8c7oM8BoDVAnwflOroNgDcQ1RE2otsAAOuMdfRBfQW+F2/rSF0biM5bOW+mbYttM3kQs29o4e394fS5MqtvXItnmmt9sPdY228vz2Hqq4s/PVL1uTS32c5QQvRaBwBRAH0elOvoNgDeQFRH2IhuAwCsM9bLB5WFoAtN06ElX4S6yDY4bB1vAcaNkAut2ljQKhd9zu69b5TLpi4VlF2ft8lYi9QBQB9RehH0eQiuo9sAeCPzk+hmLAlABQDExXr5oJ64eAHe1ou69rAUvOniuZON91oqzcWGABanrl6fm87EYnLamc7ZsRwoox/fw+7nd01oH5I6AOgjoM+Dch3dBsAbiOoIG9FtAIB1BnzQmzdQ501ddBt6igD6nLkhV+yWQ/gczpfWNpXUH8q955o3Nwx1ANBHQJ8H5Tq6DYA3ENURNqLbAADrDPigN2+gzpu66Db0FAH0uSWFfi6b6zPks+my6YdO+eGgzwFgMUCfB+U6ug2ANxDVETai2wAA6wz4oDdvoM6buug29BRx9XkukqHPAaA/gD4PynV0GwBvIKojbES3AQDWGfBBb95AnTd10W3oKQLqc/MGdehzAOgPoM+Dch3dBsAbiOoIG9FtAIB1BnzQmzdQ501ddBt6igD6vP4Q8np9zu0/L7PKQZ8DQEBAnwflOroNgDcQ1RE2otsAAOsM+KA3b6DOm7roNvQU7elz9vr0aE9K5Fao60JI0/xwZn2u52+X8tjTeyo1Dn0OAK0D+jwo19FtALyBqI6wEd0GAFhnwAe9eQN13tRFt6GnCKHPDfdUCtlBnzMnnH+Ykfzt6jnq8vnn0OcA0Bqgz4NyHd0GwBuI6ggb0W0AgHUGfNCbN1DnTV10G3qKMPr8wR4Rz+rx4076/LF25jlzj5SLbvb1F9DnANA+oM+Dch3dBsAbiOoIG9FtAIB1BnzQmzdQ501ddBt6ij5Tl+vzxZX2+lEHAP6APg/KdXQbAG8gqiNsRLcBANYZ8EFv3kCdN3XRbegp+kJdOTFeqvFy3l6Zigd1ANAxoM+Dch3dBsAbiOoIG9FtAIB1BnzQmzdQ501ddBt6it5Qpy6Pry45ozuoA4DuAX0elOvoNgDeQFRH2IhuAwCsM+CD3ryBOm/qotvQU/SJujIPfHkpu9NBHQCEAPR5UK6j2wB4A1EdYSO6DQCwzoAPevMG6rypi25DTwHqQB0ANAL0eVCuo9sAeANRHWEjug0AsM6AD3rzBuq8qYtuQ08B6kAdADRCpc/5PSe4cOHChQsXLly4cOHChQsXroDXYJgIoFMIEd8GwBvZFd2MJQGoAIC4gA968wbqvKmLbkNPAepAHQA0AvR5UK6j2wB4A1EdYSO6DQCwzoAPevMG6rypi25DTwHqQB0ANAL0eVCuo9sAeANRHWEjug0AsM6AD3rzBuq8qYtuQ08B6kAdADQC9HlQrqPbAHgDUR1hI7oNALDOgA968wbqvKmLbkNPAepAHQA0AvR5UK6j2wB4A1EdYSO6DQCwzoAPevMG6rypi25DTwHqQB0ANAL0eVCuo9sAeANRHWEjug0AsM6AD3rzBuq8qYtuQ08B6kAdADQC9HlQrqPbAHgDUR1hI7oNwLLjQAwGYucothkrCvigN2+gzpu66Db0FKAO1AFAI7Stz4/2NgaDwfZD7auHW4PyuqdHbIe79/Ivbc8yD8r3bOw+UT98srOZP7l1QB/Z3y7M2dw7NP2cg/tmq3y4jl7eFmwNxEDDflVA0uebQmHswPxVIoaJ2NnMv9VLoXpWf/BIbEiWkKKX7dk3/LmB6fHszduNi6+LEtzfNjNgJ/aAL6l6YtvAklfmlUFWPWjhhscB57wOlkOfd4cWfTDrf/kizvr0AdeTlv2j4dn97bruXu5b1T9UPFh14jWddRPeOmy+6K+gZleBx+D+PvOhJciRqKheKEVW2w+HyZOd7RYoslDXFW9WVL1k2dmxLdKR2Nq1vedwN1pzFIg6pfoZXc/Z01XvU677wXqlZQs2+OarQo1gMbWKUnNqaQRkuAkc3kjj7+LcqqZSub1H1oBOtaj8CVTZSf2Ow2+0a0/FqqZBTtdoU59XFYIy9XCrKoacDpmI/e2qv9nfVh8/2tsobz7a27DVeFKKsmJ/uKX9xeK/D7cGbK/P2Lk419HL24gDRtNuFF1dJoZLR9rZlFTfgSR0DxituCW9Z0uV6PJrD3dVJXkkNqSbszvLoj/crd6ZqfF99UH6WyQpXvX0S6DP97er37hFtLSdWHVmkqg4G7EtYakr8yogHSbpsBg12zpIi09M6NYeuaK6g7gt0C5a8sEqQDFrbCacOty9V/334D7tf6uQjnbZh7v3yjvzSFfufw/u65bsb9dEck156675UmJ3SuyTnc0qvNHC9KIgTIFmHpVKjxztbci0Zze0MYRhoa6jNxthCCrk+KTCmutzOVrOqyJXwRp6ev6gFpYH0zPNqavtLv17z5rmyy5YzK3i8OC+uWVgUSNw6BBejUQ3142aSuX8Hk5Ua1OqJeSm8snOpnKnWlENfFb2WLSnOq3LdT1x0fr6dqYqHO7uKT0rmWMnlVitDUSuq9VOKvjNextqYR/u3pPvVIKJo70dRSXe0/p+k2hflOvo5W3CziYzC10Wys6mqmYPqv5yR+0Os4hc0dWSOCQ6n8j1LfOIALlZ+aOaUiWOykqLrWXQ50dCrYfqIIiV2P1tZjij/OEWYtvCMlfmpcakAPNVOpzMh5P5MElHSTqapo92xca22BiIwWb6H8ndKLkbJXfD5HaY3A2Tu1EyHyXz0TQdTdNRko4SkWE4EceT9HiSjhIxnorR4jYfGBa/uD0Ifd4R2vRBU2hytLfB94M0IuS6UTaYe7ijxmQ0GNUsOdy918r6NZm3zpqvh1uULilAPLivUqTI9WHyZGfz/pYxNH+ys3lvY9M8RFJTXq1R19GbeWSj7dz48v429Ln+6+7pupqVSU08XfACLwvju6xsDHVNes9x3jPOh0XX2UbvWdN8uQgWrlV8srNrmJW0lLVJ4GiricnNRnB1w6lS1b/nyc4m6R2e7GyadT5pKg/uV4wd7W3oVdHw62q0p/za3CTLkEEEhNDn7D3qEJSp09JWrVNCRd7/kYFk2vPZajydsc+e7aDdadRAywu69HkDeQm3/G2p8crHyU/e4qaUh4k4JH5yJDY0XS2LQ6PeUyNyKuzlWXEtdlc0J1mCfmCcBKZDAJrDb3EELoU+10vcYhKh60Bb4LBtuFMX820A+twHEzE6F6NzMZoQpKNJOjyfH5/fDie3o8l8lMzH0/TvBuI30/mvt8VgIH765c14ejOeXo+n1+PpzXg6G09noySVPfpkKsZJOjxPj8/SP//CurlDm4DKXVX6NvMasrJUGSEyNFBb5cYK6PMuEUCflzMVXJTPTA1xsV3NRBANAFRL9rfbD5g6bMmPnjCTB/K0mBpXqL/9yc5mHskwEdTB/cH2Q7KOICsdGgev0Pr2rJExiYEtvbtcb33OyA92NquRpydiWfR5s95zfnIxH0/no+R2OMm6Tr33vM1E+ziZn0xTufc8PktHE3F6IUbTGtvswpgTLA6tIh3I01EjcNRRgyc7m27TwmzdcKlU9e95okkMVVSrK7C0plIiVmtj5RUNxZp/E3ukgNSJ2KO9jYC7NlwQQ58rE+aMGK46Ib2YqQ4vVqqTz7XbTIZp4rz8o9U6jbbiA/cGWl6uXG20LiSWPB2aCfWMzFK0b2zmXRpZ+y2L0upmrj+TF5CT++0zaYpaPhIb2vtLG/SNtfoidnaBuvHPsTjgn102fV4jzrlfKgskmeRaYlsB9LkPrBHGKJlXw/yT2z//Umz84vb4/Hp0kA4GYvCj+cnl9enLm9OXs9OXs5OL2ego3RiIf/qv7745uz7+fToYiO/tinEixon49bYYbItxIk6m4qdyIyCNc2W1YmNX0uSbxagcmbZSN5sME7Gzqe7LUBuZvDYeia1N6PMO0bk+J1up7avQmT7XSZ/TLrh6s8NEjS9vwZovaScds0pf5SefYuJWt+ZzTfQN5ZLRIDJpGLjZL9qlBhHzmuvz+q3RzT09EVzw3P72z3rqmvSex+c335x9d3x+PUpuxtObk8sb2nsm18PJ9Tdn331zdn18Phsld1nXOU7y12a9Z+3qM6X5aqVVrBfnLgKnJuGX+U8zZVpfqdzeQ96pDWQoy/WdJ03JPLxVn+s7DuRV96FaUXdE0OfqiLg2DkT1OTNIL28YKMZUGH2u1g9qmFTn7qmTjdmH9/el/7Yi0d0baKIe6cJvbWFz+UmmzYjEzf9LFqlap7bYOedSMFu8fUv+Vgvrh0Sfq4KTkZFFD80MIhw4jRfIq/QtDDsWXxddrDwM4UqsRoK69ciB2IUBfe4DhwhjPJ2Pp/PhZL6zKXb++3qUzJ6+TH/+fTEYiH95k569FedX4uyteP5t+rPPxPd274aTm+Pzm+Pzu51NMfhhOk7EyYEYDMRvL8TJVIwmiqfLunqopjwg6Q+UJTPEkQ+Md5JhJuw/7xQh1rdL3yrBmWHDeWN9rk9ZZJZsa+9vlbdAzZc6R6QLb1afM0l2i0l4Zh++HF+2ugvARF0I3vKfpkxLmMCmg6261AMuH401nW3vqSvENu8+TT09EXxmr4Bixl2fF73n7fH59fF51nvOn79OX7xJX6i959OXd+PprOg9Z8fns+H5PNPkpxfitOw966k2LMOWysK1VZRGSWqaPgeBM9S0TD0sdcNeqRrVsdxai1V6tm+zPpcWKNXCsBqrLvFHPATX53SrwCL6XNrr1VyfV6WrSHS9HrS2F929gSbLwmUxqQtLeZKc7GFW4mM9yDYpW27OOV/TXghm9kE6676gPi9kQN4Bs3Laag9Zpc+a0aj4OuxiC6XNxrL6coahtKadJMuBPl9e2COMyd1wUqy4OxCDH6XPXs3P3qTJO/HXX4nBQGz/u7j4KC4+iukHkbwT2wPxwz+mL17Pn77MgpK747O70SR9tCsGn4n/vBDjRAzPFQMsZzSwW1HKmXA9WSNBdifNdID17V0inD5PRDEvoXaUdEVl4/Xt8vSybEmWUKajmCmYPqdzRHmMS/IVqevbKzJlqvN/G/LkKUm2O90/uYT6XMHaz58Xy4+LKmGIeJt4urDMn4eRNE76XO49p/PTy3nZe15+FNP3YvpB6T0nV+nZG6b3HCe5Ptd7Tx20+VpQn6vcKou9q+vezpGLwCnWtBOBQxZK8GuHm1eqpnWsRlQ30OdMD2ICu029GGHJSV6yKfTA+lwfNTGsb88+MSwXKeZqzIlMDcs/LAOKxVfW8YKFuXa9WRbP6k5jXVjKc+Y2fa6ufCYz7eSFWpildJNkRWtlM1G8hvXt2SemZdj70rPEcqMIN4htVtaaaHQpvm67WLWgbcQWNysZ9Qu6aohtCdDnPrDvoJvcDSe3w8nteJr+7DNutucH4ssPYprh/8RnA/HZr8TFBzG5Es+/TU8v0+Hkbnh+l+1X/00iRpN0eJ5W2XRUnyJw1+fGvRi6v0Ofd4mw+lwPCvWzl1zywynfMj1yZUnx/g4StQZpvrgESPrpa2p+uH35tuwrmtjZFIrYDltqkbrueSu5wvr2powpy3fZITMvT2ejejpC1zl1rr3n/Nmr9OyNmL4Xlx/Fy7+Jl38TF2W/meG9uPiQg/Seo8m8WOWu9p4amObLKljkB+vWnCuTgiZ9bhE4yqp7OVOAhz53qVQEdXWsTlQb1rfzR9k5SjP2TmULVbakem3zw+kZ/PKiMuaH02thNUDFHqY3UL51yw+n1mzrfviFuXa/2bS7mJ7CxW1WN+nzoTqB5r64napZfWL8SGy4bPOWHtRtkyd+dZFJ9YPDV6bF7YxhbsXXdRfLJFo3EKsccac+aye2LUCf+6BmBiBfoff0f8Tm98WX78Xlx3zsf3Ilfv8TMRiIn//v/MXr+dmb+flbsT0Qgx+Iv34Ulx9F8k68eC1OLuaj5Pbwl2IwEFt/yLPmVH+dGy8r0Uyfs0Ez9HlYhNbntoy7/F5xWyRa7k2zWlLEps5bKN14CySW7CMLTDp3kvvt3s6RwjkJRQ537zOnNLlMcC1AXee8SdhpmsBivfW5LZYu4ePpfFQfTM+4zZ8XvefLSpyXvef52/TszfzF67L3TCdX4uJDfo/cew7P74oXqr0nAdt82QQL4c0hK4et9bAKHDcz2B+l1w2nSuXwHtV4h+x3pvxw5A85tXW89tQLoo720Aimz2nXXnUti5+vljA10nr8gG5zZYBWZg7V0ZlrxzsPd417qvWZZPvQtc0AAAakSURBVDmwtutz/RA1BtxsrT4oQPeZq9/ubEs5qLzOV9On9y1J48muWpNV9BctpT6n2+8NxNJT37WUXThfbRlhjTDGSXp6mT57JX7/E7H9p2wNnjh7kz57NT+9nJ/+m8iyxI2ns5OL2enlPNuUvvnPeZyRvBO/+7H47cV89Id8AO7Xk/lokg6TKmzNqg3JJlitb5crmyytua0xSvUr3k8bCu+D2QAHRJg/N2bo4btIYyRK46qHW5YcS8We2LYqUhh9zq8OkMm0H0GUz3rd2yDxj3q+mvYnzOsEW6Kua94UWJe4b+mfQ59reqN+jlcH9XRzcuWlmT8ve8+zNyJ5p/Wel3cnF7cnF7Oi97x7/m169kaUKj15J55/K04u5qPJ3fA8n0jPe08d5ubL93w1pijtXmw/QJomsHDMTG7U53WVyuE9ZvZMb7Bu7C8scah+Ru2ZDTB1epbnggijz/WFcEqtlSqx9dgAyyCQfb2H2heqpaIfeackALQK+8ZcO97Jpjwpf7iyvFw7/Vv/r5zkqTY/CjvnXKV6Ll9LDkLjNqOW1rKzcENVrrMHelefyD/zQDOGU9rsseeyVdH1OTm1bmeT2b1vJPZA2ZPPjsvwxLYE6HMf2COMafrsVTr5kxj8QPzlgzh7I56+nI+S2XByM5zcjJK7rFnY+kP239nJv2ru/A9ZkJHqDYjsOwrUAx3kIZ6qskkT4zuSztffn29Nl5NlmPI7Aguja32uBiv8pId9Do2PROWUZsUljf6YzuAdtDVZF0SfW+aI9P295efKI7r+IbGyTn5ba/0s1HXMGwWflVbd3lVhvfU5PfOMDZh9PN2ce2xpzlfLe8+rfNW61nvm/yj/e3Jxd3o5f/oyPX8rLj+WC93FyUWWXm42nNyOWXvszZeDYGFaRVVRux1XbhQ4Q9p0OE8xWnL72yuVy3uS0hjDiK3xhGzDmCM/Xkzyt9u1p5oBxOHY+cBoU58rWfhJ5dAvPtMgV42qLRPmasGlYZDXwLPj8eZ3yja31ts1mj9ndp9qO8DJLBY5Ak0/EY2V/VQTWo4Z12J6XvObD13nFkAaRwrIy/cNn5vciU1Br3Pr7o3tR3WqWGIT19uIlR/X2LMRG7YyAxXqIozf/bgq07//YzpKZtkhMSd/Sb8n14TP0kfT2/H0dvRlWtWTfxTT9+L8rXj6Mh1P5/IGGWPVkoaosmU45VNEUZef72ufkPfL/rWP+fMu0ZIPkg6aO75L7wfLTtkYR6ob0JTwTr+qTZV616xuv7SGAc68dd58cXNEllEG5TfKWW9NvG3uHSbicHdvn8RdHeulWM0+DV0ajq0vAwJRpzgRl+ypmacbondDNe6Wurre8/m36cUH8fpavPybePFa6j0v7sbTWx2j6e0omT17dZdtR5d7zyzV3Hg6HybqFLql+WKKQG+pDK2i+rkzsQaBk4ih2qQ4vNBcN2oqVZP3JOZFWPqBINKrWPsNC5Rkfe6iPb0OoguF1ufPARvXjneyo7zl2mZvMG+oG28GSgTatdgTgAofWCOMZ6/S5J2YvhfT99lA/m026j9KZqPktjzcVcVslMzG09unL+/O34rp+2ydXjqe3h6fXw8nN+PpfJQYFumpsOR3AJYT8EFv3kCdN3XRbegpQN2i1C1x7wkAXQD6PCjXTney+boTsb/YNBS/3vtI7C/ZiNHSAlEdYSO6Df2DNcJ48ToPL87fiqcvRRY9ZAHEKJlZIozsnuzxItXNHfT5ygM+6M0bqPOmLroNPQWoW5S6Je49AaALQJ8H5drlNvYsMUsqckcwh6JZM6gBBIjqCBvRbegfFo0w5hKyCON2lNyOktl4Onv+bZ4X5+yNOL2cj5Kb4eR6lNwOE3MSWgl6DkhgyQEf9OYN1HlTF92GngLULUrdEveeANAFoM+Dcu14p77/vJV9EXQTF8LxJkBUR9iIbkP/4B9h3I6S6tyX0SSV5wGGk9tRMstS3STvxPlb8ezV/ORiNpx8N5xc10cYpkQPwHIDPujNG6jzpi66DT0FqFuUuuXsPQGgM0CfB+U6ug2ANxDVETai29A/+EcYanihBhnDyWw4uTm9nJ+/FZMrMbkSL16np5e3o+T6m7Pvjid38X840AHgg968gTpv6qLb0FOAukWpQ+8JrBkqfS5w4cKFCxcuXLhw4cKFCxcuXLEvzJ+HGAuJbgPgjeyKbsaSAFT4YNEZAPoIv0LvSjz79u7k8maYfBpOPg0TzACsJuCD3ryBOm/qotvQU4C6RalD7wmsGcrr/wEwCfzfdLPRGgAAAABJRU5ErkJggg==" alt="" width="715" height="38" />

 #include <stdio.h>
#include <string.h>
#define mem(a) memset(a,0,sizeof(a))
#define MIN(a,b) ((a) < (b) ? (a) : (b)) int DP[][],cost[],N,M;
char str[]; int main()
{
while(~scanf("%d%d", &M, &N))
{
mem(DP); mem(str); mem(cost);
scanf("%s%*c",str);
char ch; int x, y;
for(int i=;i<M;i++)
{
scanf("%c %d %d%*c", &ch, &x, &y);
cost[ch-'a'] = MIN(x,y);
}
for(int i=;i<N;i++)
{
for(int j=i-;j>=;j--)
{
DP[j][i] = MIN(DP[j+][i]+cost[str[j]-'a'], DP[j][i-]+cost[str[i]-'a']);
if(str[i] == str[j])DP[j][i] = MIN(DP[j][i],DP[j+][i-]);
}
}
printf("%d\n", DP[][N-]);
}
return ;
}