百度网盘网站开发文档模板,建设环境工程技术中心网站,wordpress的app,牟平网站建设1 /*2 题意#xff1a;给出一串字符(全部是小写字母)#xff0c;添加或删除一个字符#xff0c;都会产生一定的花费。3 那么#xff0c;将字符串变成回文串的最小花费是多少呢#xff1f; 4 5 思路#xff1a;如果一个字符串增加一个字符 x可以形成一个回文串… 1 /*2 题意给出一串字符(全部是小写字母)添加或删除一个字符都会产生一定的花费。3 那么将字符串变成回文串的最小花费是多少呢 4 5 思路如果一个字符串增加一个字符 x可以形成一个回文串那么从这个字符串中删除这个字符 x6 同样也能形成回文串7 所以我们只记录删除和增加这个字符 x 的最小的费用就好了-转变成添加多少个字符形成回文串费用最少 8 9 str[i]!str[k]
10 dp[i][j]min(dp[i][j-1]cost[str[k]-a], dp[i1][j-1]cost[str[i]-a]) ;
11
12 str[i]str[k]
13 dp[i][j]dp[i1][j-2];
14
15 */
16 #includeiostream
17 #includecstring
18 #includecstdio
19 #includealgorithm
20 #define N 2005
21 using namespace std;
22
23 int dp[N][N];
24
25 int cost[30];
26
27 char str[N];
28
29 int main(){
30 int m, n;
31 while(scanf(%d%d, m, n)!EOF){
32 scanf(%s, str1);
33 memset(cost, 0, sizeof(cost));
34 while(m--){
35 char ch;
36 int a, b;
37 getchar();
38 scanf(%c %d %d, ch, a, b);
39 cost[ch-a]min(a, b);
40 }
41 for(int i1; in; i)
42 dp[i][1]0;
43 for(int j2; jn; j)
44 for(int i1; ij-1n; i){
45 int kij-1;
46 if(str[i]!str[k])
47 dp[i][j]min(dp[i][j-1]cost[str[k]-a], dp[i1][j-1]cost[str[i]-a]) ;
48 else dp[i][j]dp[i1][j-2];
49 }
50
51 printf(%d\n, dp[1][n]);
52 }
53 return 0;
54 } 转载于:https://www.cnblogs.com/hujunzheng/p/3936088.html
