POJ 3280 Cheapest Palindrome
POJは制約が多すぎる (unordered_mapが使えなかった)
問題概要
- N種類の文字で構成された長さMの文字列Sが与えられる
- この文字列にいくつかの文字を追加、あるいは削除して回文にする
- i番目の文字を追加するには、a_iのコスト、削除するにはb_iのコストがかかる
解法
- abbbbを回分にする時aを追加して、abbbbaとする方法と、aを削除してbbbbとする方法どちらでも可である
- 従って、追加 or 削除はコストの低い方を用いる
- dp[i][j]:=区間[i,j)を回文にするコストとすると
- ある、長さlenの区間について
- dp[i][j+1] = max(dp[i][j+1], dp[i][j]+S[j]のコスト)
- dp[i-1][j] = max(dp[i-1][j], dp[i][j]+S[i-1]のコスト)
- if (S[i-1]==S[j]) dp[i-1][j+1] = max(dp[i-1][j+1],dp[i][j])
- 以上のdpを区間lenが0 ~ M-1の間繰り返す
