Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SPOJ 9637 - Black and White [BANDW] (この記事を編集する[管理者用])

Source

Argentinian Programming Tournament 2011
SPOJ 9637 [BANDW]

問題概要

文字列SとTが与えられる.
各文字列は同じ長さ (500以下) で,アルファベットのWとBのみを含む.
以下の変換を行なって,SをTにしたい.最小の変換回数を求める問題.
 連続する区間を選び,それに含まれるWを全てBに変えて,Bを全てWに変える.

解法

各場所に対して,SとTが一致しているなら0,一致していないなら1として,全部0にするのと同じ事になる.
0が連続してる場所,1が連続してる場所を分断する必要はないので一文字だと思って良い.
101→001→000にするのも,101→010→000にするのも同じで,1回の変換で,どうやっても1を1つしか減らすことができないので,1の数が答え.
つまり,最初に一致していない場所の連続,の数が答えになる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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