papamelong308.最廉价的回文串CheapestPalindrome

作者：男人邦121121121 | 来源：互联网 | 2023-05-19 06:32

https:www.papamelon.comproblem308给定一个长度为m(m≤2000)的小写字母字符串,在给定组成该字符串的n(n≤26)个字符的添加和删除费用,求使原

https://www.papamelon.com/problem/308

给定一个长度为 m(m≤2000) 的小写字母字符串, 在给定组成该字符串的 n(n≤26) 个字符的添加和删除费用, 求使原字符串变为回文串的最小费用。输入第一行包含两个整数 n 和 m 第二行为长度为 m 的字符串, 接下来有 n 行, 每行首先是一个小写字母接下来有两个整数分别表示添加和删除该字母的费用(空格隔开) 输出一个整数，表示把字符串变为回文串的最小费用样例 1 输入 3 4 abcb a 1000 1100 b 350 700 c 200 800 输出 900

解答

#include #include #include #include #include #include using namespace std; int n, m; string s; map> mm; const int N = 2010; int dp[N][N]; int main() { cin >> n >> m; cin >> s; for (int i = 0; i char c; int add, rm; cin >> c >> add >> rm; mm[c].push_back(add); mm[c].push_back(rm); } memset(dp, 0x3f, sizeof dp); s.insert(s.begin(), '#'); for (int i = 0; i <= m; i++) { dp[i][i] = 0; } for (int i = m; i >= 1; i--) { for (int len = 1; i + len <= m; len++) { int j = i + len; if (s[i] == s[j]) { if (i <(j - 1)) { dp[i][j] = dp[i + 1][j - 1]; } else { dp[i][j] = 0; } } else { //字符串两边不相同 char a = s[i]; char b = s[j]; dp[i][j] = min(dp[i][j], dp[i + 1][j] + min(mm[a][0], mm[a][1])); dp[i][j] = min(dp[i][j], dp[i][j - 1] + min(mm[b][0], mm[b][1])); } } } cout < return 0; }

我的视频题解空间

推荐阅读

string
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新 2023-12-12 13:59:33
format
VScode格式化文档换行或不换行的设置方法

本文介绍了在VScode中设置格式化文档换行或不换行的方法，包括使用插件和修改settings.json文件的内容。详细步骤为：找到settings.json文件，将其中的代码替换为指定的代码。 ... [详细]

蜡笔小新 2023-12-14 17:15:38
数组
文件压缩解压的哈夫曼树实现

本文介绍了使用哈夫曼树实现文件压缩和解压的方法。首先对数据结构课程设计中的代码进行了分析，包括使用时间调用、常量定义和统计文件中各个字符时相关的结构体。然后讨论了哈夫曼树的实现原理和算法。最后介绍了文件压缩和解压的具体步骤，包括字符统计、构建哈夫曼树、生成编码表、编码和解码过程。通过实例演示了文件压缩和解压的效果。本文的内容对于理解哈夫曼树的实现原理和应用具有一定的参考价值。 ... [详细]

蜡笔小新 2023-12-11 14:13:46
string
Codeforces Round #321 (Div. 2) Kefa and Dishes 状压+spfa

本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes，通过状压和spfa算法解决了这个问题。给定一个有向图，求在不超过m步的情况下，能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ... [详细]

蜡笔小新 2023-12-11 10:37:34
uri
向QTextEdit拖放文件的方法及实现步骤

本文介绍了在使用QTextEdit时如何实现拖放文件的功能，包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数，并结合QMimeData和QUrl等类，可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]

蜡笔小新 2023-12-14 16:06:38
uri
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
string
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
string
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
数组
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
replace
Java String与StringBuffer的区别及其应用场景

本文主要介绍了Java中String和StringBuffer的区别，String是不可变的，而StringBuffer是可变的。StringBuffer在进行字符串处理时不生成新的对象，内存使用上要优于String类。因此，在需要频繁对字符串进行修改的情况下，使用StringBuffer更加适合。同时，文章还介绍了String和StringBuffer的应用场景。 ... [详细]

蜡笔小新 2023-12-13 19:21:06
replace
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
fetch
游标的使用笔记

本文介绍了游标的使用方法，并以一个水果供应商数据库为例进行了说明。首先创建了一个名为fruits的表，包含了水果的id、供应商id、名称和价格等字段。然后使用游标查询了水果的名称和价格，并将结果输出。最后对游标进行了关闭操作。通过本文可以了解到游标在数据库操作中的应用。 ... [详细]

蜡笔小新 2023-12-13 15:24:30
byte
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11
list
开发笔记：实验7的文件读写操作

本文介绍了使用C++的ofstream和ifstream类进行文件读写操作的方法，包括创建文件、写入文件和读取文件的过程。同时还介绍了如何判断文件是否成功打开和关闭文件的方法。通过本文的学习，读者可以了解如何在C++中进行文件读写操作。 ... [详细]

蜡笔小新 2023-12-12 17:48:18
byte
Oracle 11g物理Active Data Guard实时查询（Realtime query）特性

在Oracle11g以前版本中的的DataGuard物理备用数据库，可以以只读的方式打开数据库，但此时MediaRecovery利用日志进行数据同步的过 ... [详细]

蜡笔小新 2023-12-11 15:49:10

男人邦121121121

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章