首页 > 代码库 > POJ 3280 Cheapest Palindrome
POJ 3280 Cheapest Palindrome
记忆化搜索，$dp$。
$dp[L][R]$表示将区间$[L,R]$修改为一个回文串需要的最小代价。转移很容易写，区间$dp$或者记忆化搜索都可以。
区间$dp$：
#include <cstdio>#include <cmath>#include <set>#include <cstring>#include <algorithm>using namespace std;char s[2010],op[5];int dp[2010][2010];int c[30][2];int m,n;int main(){ while(~scanf("%d%d",&m,&n)) { scanf("%s",s); for(int i=0;i<m;i++) { scanf("%s",op); scanf("%d%d",&c[op[0]-‘a‘][0],&c[op[0]-‘a‘][1]); } int len=strlen(s); for(int L=0;L<len;L++) { for(int R=L;R<len;R++) { dp[L][R]=0x7FFFFFFF; } } for(int x = 1;x<=len;x++) { for(int L=0;L<len;L++) { if(x==1) { dp[L][L]=0; continue; } int R = L+x-1; if(R>=len) continue; if(x==2&&s[L]==s[R]) { dp[L][R]=0; continue; } if(s[L]==s[R]) dp[L][R] = min(dp[L][R],dp[L+1][R-1]); dp[L][R] = min(dp[L][R], dp[L+1][R]+c[s[L]-‘a‘][0]); dp[L][R] = min(dp[L][R], dp[L+1][R]+c[s[L]-‘a‘][1]); dp[L][R] = min(dp[L][R], dp[L][R-1]+c[s[R]-‘a‘][0]); dp[L][R] = min(dp[L][R], dp[L][R-1]+c[s[R]-‘a‘][1]); } } printf("%d\n",dp[0][n-1]); } return 0;}
记忆化搜索：
#include <cstdio>#include <cmath>#include <set>#include <cstring>#include <algorithm>using namespace std;char s[2010],op[5];int dp[2010][2010];int c[30][2];int m,n,len;int dfs(int L,int R){ if(dp[L][R]!=0x7FFFFFFF) return dp[L][R]; if(R-L==0) dp[L][R]=0; else if(R-L==1&&s[L]==s[R]) dp[L][R]=0; else { int mn = 0x7FFFFFFF; if(s[L]==s[R]) mn = min(mn,dfs(L+1,R-1)); mn = min(mn , dfs(L+1,R)+c[s[L]-‘a‘][0]); mn = min(mn , dfs(L+1,R)+c[s[L]-‘a‘][1]); mn = min(mn , dfs(L,R-1)+c[s[R]-‘a‘][0]); mn = min(mn , dfs(L,R-1)+c[s[R]-‘a‘][1]); dp[L][R] = mn; } return dp[L][R];}int main(){ while(~scanf("%d%d",&m,&n)) { scanf("%s",s); for(int i=0;i<m;i++) { scanf("%s",op); scanf("%d%d",&c[op[0]-‘a‘][0],&c[op[0]-‘a‘][1]); } len=strlen(s); for(int L=0;L<len;L++) { for(int R=L;R<len;R++) { dp[L][R]=0x7FFFFFFF; } } printf("%d\n",dfs(0,n-1)); } return 0;}
POJ 3280 Cheapest Palindrome
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。