首页 > 代码库 > POJ 3280 Cheapest Palindrome(DP)
POJ 3280 Cheapest Palindrome(DP)
题目链接
题意 :给你一个字符串,让你删除或添加某些字母让这个字符串变成回文串,删除或添加某个字母要付出相应的代价,问你变成回文所需要的最小的代价是多少。
思路 :DP[i][j]代表的是 i 到 j 这一段位置变成回文所需的最小的代价。
1 //3280 2 #include <stdio.h> 3 #include <string.h> 4 #include <iostream> 5 6 using namespace std ; 7 8 char sh[2100] ; 9 int minn[2100] ;10 int dp[2100][2100] ;11 12 int main()13 {14 int M,N ;15 while(~scanf("%d %d",&N,&M))16 {17 scanf("%s",sh) ;18 getchar() ;19 char ch ;20 int inser,delet ;21 for(int i = 0 ; i < N ; i++)22 {23 scanf("%c%*c%d %d",&ch,&inser,&delet) ;24 minn[ch-‘a‘] = min(inser,delet) ;25 getchar() ;26 }27 for(int i = M-1 ; i >= 0 ; i--)28 {29 for(int j = i+1 ; j <= M-1 ; j++)30 {31 if(sh[i] == sh[j])32 dp[i][j] = dp[i+1][j-1] ;33 else34 dp[i][j] = min(dp[i+1][j]+minn[sh[i]-‘a‘],dp[i][j-1]+minn[sh[j]-‘a‘]) ;35 }36 }37 printf("%d\n",dp[0][M-1]) ;38 }39 return 0 ;40 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。