【题意】
给定一个长度为m(m<=2000)的小写字母字符串,在给定组成该字符串的n(n<=26)个字符的添加和删除费用,求使原字符串变为回文串的最小费用
【输入】
第一行n,m
第二行原字符串
接下来n行开头一个小写字母,然后两个数字分别表示添加删除该字母的费用
【输出】
输出一个数字,表示最小费用
动态规划
用f[i][j]表示将i到j变为回文串的最小费用
转移方程为
f[i,j]=min(f[i+1,j]+min(costd[s[i]],costi[s[i]]),f[i,j-1]+min(costd[s[j]],costi[s[j]]))
若s[i]=s[j]则还需考虑f[i+1,j-1]的值
program poj3280;
var
n,......
阅读全文