1 /* 2 題意：給出一串字符(全部是小寫字母)，添加或刪除一個字符，都會產生一定的花費。 3 那么，將字符串變成回文串的最小花費是多少呢？ 4 5 思路：如果一個字符串增加一個字符 x可以形成一個回文串，那么從這個字符串中刪除這個字符 x 6 同樣也能形成回文串！ 7 所以我們只記錄刪除，和增加這個字符 x 的最小的費用就好了！->轉變成添加多少個字符形成回文串費用最少！ 8 9 str[i]!=str[k] 10 dp[i][j]=min(dp[i][j-1]+cost[str[k]-'a'], dp[i+1][j-1]+cost[str[i]-'a']) ; 11 12 str[i]==str[k] 13 dp[i][j]=dp[i+1][j-2]; 14 15 */ 16 #include<iostream> 17 #include<cstring> 18 #include<cstdio> 19 #include<algorithm> 20 #define N 2005 21 using namespace std; 22 23 int dp[N][N]; 24 25 int cost[30]; 26 27 char str[N]; 28 29 int main(){ 30 int m, n; 31 while(scanf("%d%d", &m, &n)!=EOF){ 32 scanf("%s", str+1); 33 memset(cost, 0, sizeof(cost)); 34 while(m--){ 35 char ch; 36 int a, b; 37 getchar(); 38 scanf("%c %d %d", &ch, &a, &b); 39 cost[ch-'a']=min(a, b); 40 } 41 for(int i=1; i<=n; ++i) 42 dp[i][1]=0; 43 for(int j=2; j<=n; ++j) 44 for(int i=1; i+j-1<=n; ++i){ 45 int k=i+j-1; 46 if(str[i]!=str[k]) 47 dp[i][j]=min(dp[i][j-1]+cost[str[k]-'a'], dp[i+1][j-1]+cost[str[i]-'a']) ; 48 else dp[i][j]=dp[i+1][j-2]; 49 } 50 51 printf("%d\n", dp[1][n]); 52 } 53 return 0; 54 }
?
)
)
