WARush

SRMの結果とか、解けた問題のコードを書いていきます

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 );
    }
};