字符串DP dp[i][j]表示在区间i j范围内构成回文的最小花费
应为删除一个字符和添加一个字符时等价的,所以考虑最小的一种即可
如果当前匹配的两个字符相等,即str[i] == str[j] 那么dp[i][j] = dp[i+1][j-1](显而易见)
如果不等
则把左边添加删除一个右边的值
或者在右边添加删除一个左边的值 ,取一个最小的即可
CODE:
/*DP*/ /*注意:插入和删除是等效的,去较小的一个即可*/ /*AC代码:79ms*/ #include <iostream> #define min(a,b) (a<b?a:b) int dp[2005][2005]; char str[2005]; int cost[27]; int N,M; void Solve() { int i,j; memset(dp,0,sizeof(dp)); for(i=M-1;i>=0;i--)//要倒着来 { for(j=i;j<M;j++) { if(str[i]==str[j]) dp[i][j]=dp[i+1][j-1]; else dp[i][j]=min(dp[i+1][j]+cost[str[i]-'a'],dp[i][j-1]+cost[str[j]-'a']); } } printf("%d\n",dp[0][M-1]); } int main() { int x,y,i; char s[2]; while(scanf("%d%d",&N,&M)!=EOF) { scanf("%s",str); for(i=1;i<=N;i++) { scanf("%s%d%d",s,&x,&y); cost[s[0]-'a']=min(x,y); } Solve(); } return 0; }