典型的DP。
首先用一个DP判断s[i…i+l]是否回文，这可以根据s[i+1…i+l-1]是否回文以及s[i]==s[i+l]得到。这里最外层循环是l，也即回文串的长度。随后是要计算将s[1…i-1]和s[i+l+1…m]转化成完全相同的最小花费，这里可以用另一个DP预处理得到。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<cstdio> #include<cstring> int n,m,a[26],d[26],mn,dp[2001][2001]; char s[2002],p[2001][2001]; inline bool isp(int l,int r) { if(l>=r) return true; return p[l][r]; } inline int min(int a,int b) { return a<b?a:b; } int main() { int i,j,k,l; char c[2]; while(~scanf("%d%d",&n,&m)) { scanf("%s",s+1); memset(p,0,sizeof p); mn=0x7fffffff; for(i=0;i<n;i++) { scanf("%s%d%d",c,&j,&k); l=c[0]-'a'; a[l]=j; d[l]=k; } for(i=1;i<m;i++) { dp[i][0]=dp[i-1][0]+min(a[s[i]-'a'],d[s[i]-'a']); dp[0][i]=dp[0][i-1]+min(a[s[m+1-i]-'a'],d[s[m+1-i]-'a']); } for(i=1;i<m;i++) { for(j=1;j+i<m;j++) { if(s[i]==s[m+1-j]) dp[i][j]=dp[i-1][j-1]; else dp[i][j]=min( dp[i-1][j]+min(a[s[i]-'a'],d[s[i]-'a']), dp[i][j-1]+min(a[s[m+1-j]-'a'], d[s[m+1-j]-'a'])); } } for(l=0;l<m;l++) { for(i=1;i+l<=m;i++) { if(isp(i+1,i+l-1)&&s[i]==s[i+l]) { p[i][i+l]=1; mn=min(dp[i-1][m-i-l],mn); } } } printf("%d\n",mn); } return 0; } |