題目鏈接

題意

給定一個字符串，和修改每個字母（增加或刪除）的花費，問最少花費使得構成回文串

AC

• 區間dp
  dp[ i ][ j ] 表示區間（i，j）最小的花費，從小區間推到大區間
  兩種情況：
  
• s[ i ] == s[ j ]
  dp[ i ][ j ] = dp[ i + 1 ][ j - 1 ]
• s[ i ] != s[ j ]
  dp[ i ][ j ] = min (dp[ i +1 ][ j ] + c(s[ i ]), dp[ i ][ j - 1] + c(s[ j]) )

using namespace std; int dp[2001][2001]; int main(){ #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifint n, m, x, y;char ch;string s;cin >> n >> m >> s;vector<int> c(200);for (int i = 0; i < n; ++i) {cin >> ch >> x >> y;// 刪除和加上都可以構成回文串，這里選花費最小的那種c[ch] = min(x, y);}mem(dp, 0);for (int i = 1; i < m; ++i) {for (int j = 0, k = i; k < m; ++j, ++k) {if (s[j] == s[k]) dp[j][k] = dp[j + 1][k - 1];else dp[j][k] = min(dp[j + 1][k] + c[s[j]], dp[j][k - 1] + c[s[k]]);}}cout << dp[0][m - 1] << endl;return 0; }

總結

以上是生活随笔為你收集整理的POJ 3280 Cheapest Palindrome的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。