FC2ブログ

スポンサーサイト

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

SRM 400 DIV1 Refersal Chain

0と1で構成されたある文字列のi番目からj番目を反転(配列の並びを逆転)させて、目的の文字列にすることは可能か?可能ならば最小の反転回数を、不可能ならば-1を返せ、という問題。
ただし反転操作reverse(i,j)のi,jにはi0<=i1...im, j0>=j1...jm、という制限が付く。

最初は幅優先で探索した。そちらでも通った。がDPが想定回答らしい。

d[L][I][J][R] は ( R ? init.substr(I,L) : reverse(init.substr(I,L)) ) と goal.substr(J,L) を一致させる反転回数。

xyz と abc を一致させるための回数は
1) x == a なら yz と bc の一致回数
2) x == c なら yz と ab の一致回数+1
3) z == a なら xy と bc の一致回数+1
4) z == c なら xy と ab の一致回数
になる。



なにか余分な気がする。
スポンサーサイト

コメントの投稿

非公開コメント

検索フォーム
ユーザータグ

ICPC 2009 国内予選 ゲームプログラミング 

カテゴリ
最新記事
月別アーカイブ
最新コメント
最新トラックバック
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。