hotpepsiの練習帳

SRM 612

DP | 17:36

Div1 Easy (250) EmoticonsDiv1

問題

• 顔文字をsmiles個送り付けたい
• 入力欄全体をクリップボードへコピー、クリップボードを入力欄へ貼り付け、入力欄から1つ削除の3つの操作が可能
• 入力欄にsmiles個入力するための最小手数を求める

方針

• DFS
• Challenge Succeeded
• DP
• N個ある状態で、コピーしてK回足す -> DP[N*(1+K)]よりDP[N]+1+Kのほうが小さければ更新
• N個ある状態で、1個消す -> DP[N]よりDP[N+1]+1が小さければ更新
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_612/EmoticonsDiv1.cpp

結果

x-- 0pt 324/452nd rating 1247 -> 1209 (-38)

NまたはN+1を因数分解して作る感じっぽい。

http://togetter.com/li/641003