Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2412-017c2e78
この記事にトラックバックする(FC2ブログユーザー)

SRM306 DIV2 HARD - BlockDistance (この記事を編集する[管理者用])

Source

TopCoder SRM306 DIV2 HARD (1000pt)
Problem Statement

問題概要

1000文字以下の文字列A, Bが与えられる.
1回の操作では以下のことができる.
 Aの好きな場所に,好きな文字列(何文字でも良い)を挿入する
AをBに一致させるために必要な最小手順数を求める問題.
不可能ならそれを指摘する.

解法

DPする.状態は
 dp[a][b][fg] = Aの最初a文字,Bの最初b文字,だけが入力の時の答え
 ただし,fg=1のときは,Aの最後に何かを挿入している(次にAの最後に挿入するときにコストが掛からない)
とする.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define INF 1000000000

class BlockDistance {
public:
int minDist(vector <string> oldText, vector <string> newText) {
  int i, j, k;
  int res;
  static int dp[1111][1111][2];
  string A, B;
  int As, Bs;

  rep(i,oldText.size()) A += oldText[i];
  rep(i,newText.size()) B += newText[i];

  As = A.size();
  Bs = B.size();

  rep(i,1111) rep(j,1111) rep(k,2) dp[i][j][k] = INF;
  dp[0][0][0] = 0;

  rep(i,As+1) rep(j,Bs+1) rep(k,2) if(dp[i][j][k] != INF){
    dp[i][j+1][1] = min(dp[i][j+1][1], dp[i][j][k] + (1-k));
    if(A[i]==B[j]) dp[i+1][j+1][0] = min(dp[i+1][j+1][0], dp[i][j][k]);
  }

  res = min(dp[As][Bs][0], dp[As][Bs][1]);
  if(res == INF) res = -1;
  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2412-017c2e78
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。