Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-03-15

[][] Manthan 2011 C. Sequence of Balls(未解答) 01:52 はてなブックマーク -  Manthan 2011 C. Sequence of Balls(未解答) - 練習帳

テーマ:編集距離

問題文

 Problem - 67C - Codeforces

要約

 2 つの文字列 A, B が与えられていて,A を操作して B に変更する。許されている操作は

  • A の任意の位置に任意の 1 文字を挿入する(コストt_i)
  • A の任意の 1 文字を削除する(コストt_d)
  • A の任意の 1 文字を別の 1 文字に置き換える(コストt_r)
  • A の隣り合っている文字を交換する(コストt_e)

A を B に変更するのに要するコストの最小値を求めよ。

 A, B の文字列は 1 文字以上 4000 文字以下で文字数は異なるかもしれない。それぞれの操作のコストは 0 以上 100 以下,コストの間には 2 * t_e >= t_i + t_d の関係が成り立つ。


コード例(c++)

 交換が入っている分,通常の編集距離の問題より難しくなっています。下のコードはt_eがない場合の解答です。

LayCurseさんのコードをほぼ写経しました:http://www.codeforces.com/problemset/status/67/D

#include <iostream>
#include <string>
#include <vector>
#include <climits>

using namespace std;

vector<int > c(4);
string s,t;
int dp[4001][4001] ;

int solve(int poss, int post){
  int res = INT_MAX;
  int buf; 
  if(dp[poss][post] >= 0) 
    return dp[poss][post];
  if(poss == 0 && post == 0 ) 
    return dp[poss][post] = 0;
  if(poss == 0)
    return dp[poss][post] = c[0] * post;
  if(post == 0) 
    return dp[poss][post] = c[1] * poss;
  if(s[poss-1] == t[post-1]) 
    return dp[poss][post] = solve(poss-1, post-1);
  
  buf = solve(poss-1, post) + c[1];
  if(res > buf) res = buf;
  buf = solve(poss, post-1) + c[0];
  if(res > buf) res = buf;  
  buf = solve(poss-1, post-1) + c[2];
  if(res > buf) res = buf;
  return dp[poss][post] = res;
}

int main(){  
  for(int i = 0; i < 4; i++){
    cin >> c[i];
  }
  cin >> s >> t;
  for(size_t i = 0; i < 1 + s.size(); i++){
    for(size_t = 0; j < 1 + t.size(); j++){
      dp[i][j] = -1;
    }
  }
  cout << solve(s.size(), t.size()) << endl;
  return 0;
}

 編集距離を計算する時に用いる 2 次元の dp テーブルは,縦横がそれぞれの文字列の長さより 1 だけ大きい。