首页 > 代码库 > NYOJ 1023 还是回文
NYOJ 1023 还是回文
还是回文
时间限制：2000 ms | 内存限制：65535 KB
难度：3
- 描述
判断回文串很简单，把字符串变成回文串也不难。现在我们增加点难度，给出一串字符(全部是小写字母)，添加或删除一个字符，都会产生一定的花费。那么，将字符串变成回文串的最小花费是多少呢？
- 输入
- 多组数据
第一个有两个数n,m，分别表示字符的种数和字符串的长度
第二行给出一串字符，接下来n行，每行有一个字符(a~z)和两个整数，分别表示添加和删除这个字符的花费
所有数都不超过2000 - 输出
- 最小花费
- 样例输入
3 4abcba 1000 1100b 350 700c 200 800
- 样例输出
900
1 #include<iostream> 2 #include<cstdio> 3 #include<string.h> 4 #include<cmath> 5 using namespace std; 6 const int MAX = 2010; 7 int dp[MAX][MAX]; 8 int cost[30]; 9 char str1[MAX],str2[10];10 int main()11 {12 int n,m,i,j,a,b;13 while(~scanf("%d %d",&n,&m))14 {15 scanf("%s",str1);16 memset(dp,0,sizeof(dp));17 for(i=0;i<n;i++)18 {19 scanf("%s %d %d",str2,&a,&b);20 cost[str2[0]-‘a‘]=min(a,b);21 }22 for(j=1;j<m;j++)23 {24 for(i=j-1;i>=0;i--)25 {26 dp[i][j]=min(dp[i+1][j]+cost[str1[i]-‘a‘],dp[i][j-1]+cost[str1[j]-‘a‘]);27 if(str1[i]==str1[j])28 dp[i][j]=min(dp[i+1][j-1],dp[i][j]);29 }30 }31 printf("%d\n",dp[0][m-1]);32 }33 return 0;34 }
NYOJ 1023 还是回文
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。