前提知識
今回の問題はパッと見て、編集距離DPっぽい。
競プロの問題で、典型的な問題と形が似ている問題は、元の問題の解き方をアレンジして解く場合が多い。
そのため、編集距離を求めるDPを元にして考えていこう。
Add, Erase, Swap操作は元々あるが、Rotateが元に無い操作である。
計算量を見てみると、編集距離のDPはN^2なので、N≦100だと、ちょっと計算量が余る。
計算量的にはN^3までは行けそうなので、なにか(N)×編集距離DP(N^2)ではないかと仮定を立てる。
DPの遷移自体は複雑化する余地がなさそうなので、なにか前処理をして、DPをする。
そのなにかは、元々ない操作のRatateだろう。
まずは、回転の回数を全探索して、それぞれで編集距離DPを行い、最小値が答えになる。
ここまでは良かったが、ここからACできなかった。
「回転してから削除」よりも「削除してから回転」の方が最適なケースをどう扱おうか。
これは、DPで削除を行う遷移で、そこが回転して、末尾に持ってこられた文字であれば、
Rを引いて回転操作を打ち消すことにする。
なるほど。
solve2(r) := r回回転した後の編集距離
解説
string X, Y; int NX, NY; int A, E, S, R; //--------------------------------------------------------------------------------------------------- int dp[101][101]; int solve2(int r) { rep(x, 0, NX + 1) rep(y, 0, NY + 1) dp[x][y] = inf; dp[0][0] = 0; rep(x, 0, NX + 1) rep(y, 0, NY + 1) { // Add if (y < NY) chmin(dp[x][y + 1], dp[x][y] + A); // Erase if (x < NX) { if(NX - x <= r) chmin(dp[x + 1][y], dp[x][y] + E - R); else chmin(dp[x + 1][y], dp[x][y] + E); } // Swap if (x < NX and y < NY) chmin(dp[x + 1][y + 1], dp[x][y] + S); // ok if (x < NX and y < NY) if (X[x] == Y[y]) chmin(dp[x + 1][y + 1], dp[x][y]); } return dp[NX][NY]; } //--------------------------------------------------------------------------------------------------- void solve() { NX = X.length(); NY = Y.length(); int ans = inf; rep(r, 0, NX) { chmin(ans, solve2(r) + r * R); X = X.substr(1) + X[0]; } cout << ans << endl; } //--------------------------------------------------------------------------------------------------- void _main() { while (cin >> X) { if (X == "#") return; cin >> Y >> A >> E >> S >> R; solve(); } }
