首页 > 代码库 > POJ 3280 Cheapest Palindrome（DP）

POJ 3280 Cheapest Palindrome（DP）

2024-07-13 08:41:43   225人阅读

题目链接

题意 ：给你一个字符串，让你删除或添加某些字母让这个字符串变成回文串，删除或添加某个字母要付出相应的代价，问你变成回文所需要的最小的代价是多少。

思路 ：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 }
View Code


联系
我们