NYOJ 1023 还是回文(DP,花最少费用形成回文串)-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

NYOJ 1023 还是回文(DP,花最少费用形成回文串)

简介:
复制代码
 1 /*
 2    题意:给出一串字符(全部是小写字母),添加或删除一个字符,都会产生一定的花费。
 3    那么,将字符串变成回文串的最小花费是多少呢? 
 4    
 5    思路:如果一个字符串增加一个字符 x可以形成一个回文串,那么从这个字符串中删除这个字符 x
 6          同样也能形成回文串!
 7          所以我们只记录删除,和增加这个字符 x 的最小的费用就好了!->转变成添加多少个字符形成回文串费用最少! 
 8          
 9          str[i]!=str[k] 
10          dp[i][j]=min(dp[i][j-1]+cost[str[k]-'a'], dp[i+1][j-1]+cost[str[i]-'a']) ;
11          
12          str[i]==str[k]
13          dp[i][j]=dp[i+1][j-2];
14          
15 */
16 #include<iostream>
17 #include<cstring>
18 #include<cstdio>
19 #include<algorithm>
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", str+1);
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 i=1; i<=n; ++i)
42            dp[i][1]=0;
43         for(int j=2; j<=n; ++j)
44            for(int i=1; i+j-1<=n; ++i){
45                int k=i+j-1;
46                if(str[i]!=str[k])
47                   dp[i][j]=min(dp[i][j-1]+cost[str[k]-'a'], dp[i+1][j-1]+cost[str[i]-'a']) ;
48                else dp[i][j]=dp[i+1][j-2]; 
49            }   
50            
51         printf("%d\n", dp[1][n]);
52     } 
53     return 0;
54 } 









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3936088.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章