SRM565 Div2 Medium "MonstersValley2"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12351
訳
マナオは、モンスターが生息する谷を抜けなければならない。
彼が旅をしている間、彼は一匹ずつではあるが、何回かモンスターと遭遇することになる。
各モンスターには脅威度が正の整数で設定されている。
マナオが遭遇するであろうi番目のモンスターの脅威度は dread[i]として与えられる。
マナオにはモンスターと戦う力はない。
しかし、彼はモンスターにマグネタイトを贈り、仲魔とすることができる。
遭遇するであろうi番目のモンスターが、仲間にする時に欲するマグネタイトは、
price[i]として与えられ、その額は 1 か 2 である。
始め、マナオは独りで旅をしている。
各モンスターは、マナオが独りの時や、
脅威度が、マナオの引き連れている仲魔の合計を上回っていた場合、
マナオを攻撃してくるだろう。
言い換えれば、マナオは自分を攻撃してくるモンスターに遭遇したとき、
そのモンスターをマグネタイトで買収しなくてはならない。
攻撃してこないモンスターに遭遇した場合は、
買収して仲魔にする他、ただ通り過ぎる事もできる。
以下のような例で考えてみる。
谷に生息するモンスター 1st... ドラゴン 脅威度 : 8 必要マグネタイト : 1 2nd... ヒドラ 脅威度 : 5 必要マグネタイト : 1 3rd... キラー・ラビット 脅威度 : 10 必要マグネタイト : 2
ドラゴンと遭遇したとき、マナオは1マグネタイトを使って買収するほかない。
なぜなら彼はその時は独りで旅をしており、合計脅威度は0となっているためである。
次に、ヒドラと遭遇したとき、マナオは通り過ぎるか、彼女を買収する事ができる。
最後にキラー・ラビットと遭遇する。もし、マナオがヒドラを仲魔にしていたら、
彼のパーティーの合計脅威度はラビットのそれを上回っており、通り過ぎる事ができる。
そうでなければ、2マグネタイトを使って買収する必要がある。
つまり、最小で2マグネタイトを支払えば谷を通過することができる。
遭遇するモンスターの情報が与えられるので、谷を通過する時の、
支払うマグネタイトの最小を返せ。
制約
1 <= モンスター数 <= 20
1 <= dread[i] <= 2 * 10^9
1 <= price[i] <= 2
考えた事
モンスター数が20と少ないので、
各モンスターで買収するか?通り過ぎるか?の2通りを全て試す。
脅威度のオーバーフローに注意
ソースコード
class MonstersValley2 { int N; vector<int> D; vector<int> P; int dfs( int id, long long sum ){ if( id == N ){ return 0; } if( sum >= D[id]){ return min( dfs(id+1,sum), dfs(id+1,sum+D[id])+P[id] ); }else{ return dfs(id+1,sum+D[id])+P[id]; } } public: int minimumPrice(vector <int> dread, vector <int> price){ N = dread.size(); D = dread; P = price; return dfs( 0, 0 ); } };