SRM612 Div2 Medium "EmoticonsDiv2"
問題
TopCoder Statistics - Problem Statement
訳
あなたは待ちに待ったプログラミングコンテストを間近に迎えていたためとても嬉しくなっていた。親友に対しどれほど嬉しい事か伝えようと思っている。そこで、たくさんの笑顔のアイコンを彼にチャットでコメントしようと思っている。あなたはアイコンの数 smilesが与えられる。
すでに1個のアイコンはチャットでコメントしている。あなたはタイピングがとても遅い。そこで残りのアイコンはコピペで作ることにした。
下記の2つの操作が行える。
1. 既にコメントしているアイコンを全てクリップボードにコピーする。 2. クリップボードにあるアイコンをコメントにペーストする。
それぞれの操作は行うのに1秒かかる。コピーするとクリップボードの情報は上書きされる。ペーストはクリップボードが空の場合は行えない。コメントの一部をコピーすることはできない。
ちょうどsmilesのアイコンをコメントするのに必要な最小の秒数を返せ。
制約
2 <= smiles <= 1000
考えたこと
各操作でコピーするかペーストするかシミュレートしていく。
コメントがNを超えちゃったら終わり
コピー・・・前の操作がペーストの時のみ試す
ペースト・・・クリップボードが0じゃなければ試す
枝狩りをすれば全探索でも大丈夫みたい
ソースコード
int res; int N; class EmoticonsDiv2 { public: void rec(int num, int cnt, int clip, bool flg) { if (num == N) { res = min(res, cnt); return; } if (num > N) return; if (!flg) { // コピー rec(num, cnt + 1, num, true); } if (clip != 0) { // ペースト rec(num + clip, cnt + 1, clip, false); } } int printSmiles(int smiles) { N = smiles; res = 1000; rec(1, 0, 0, false); return res; } };