首页 > 代码库 > poj3280 Cheapest Palindrome
poj3280 Cheapest Palindrome
思路:
区间dp。添加和删除本质相同。
实现:
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 int n,m; 5 int cost[30]; 6 int dp[2005][2005]; 7 int main() 8 { 9 string s; 10 int x,y; 11 char z; 12 cin >> n >> m >> s; 13 for(int i = 0; i < n; i++) 14 { 15 cin >> z >> x >> y; 16 cost[z - ‘a‘] = min(x, y); 17 } 18 for(int i = m-1; i >= 0; i--) 19 { 20 for(int j = i+1; j < m; j++) 21 { 22 if(s[i] == s[j]) 23 { 24 dp[i][j] = dp[i+1][j-1]; 25 } 26 else 27 { 28 dp[i][j] = min(dp[i+1][j] + cost[s[i] - ‘a‘], 29 dp[i][j-1] + cost[s[j] - ‘a‘]); 30 } 31 } 32 } 33 cout << dp[0][m-1] << endl; 34 return 0; 35 }
poj3280 Cheapest Palindrome
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。