WARush

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

SRM565 Div1 Easy "MonstersValley"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12350

マナオは、モンスターが生息する谷を抜けなければならない。
彼が旅をしている間、彼は一匹ずつではあるが、何回かモンスターと遭遇することになる。
各モンスターには脅威度が正の整数で設定されている。
マナオが遭遇するであろうi番目のモンスターの脅威度は dread[i]として与えられる。

マナオにはモンスターと戦う力はない。
しかし、彼はモンスターにマグネタイトを贈り、仲魔とすることができる。
遭遇するであろうi番目のモンスターが、仲間にする時に欲するマグネタイトは、
price[i]として与えられ、その額は 1 か 2 である。

始め、マナオは独りで旅をしている。
各モンスターは、マナオが独りの時や、
脅威度が、マナオの引き連れている仲魔の合計を上回っていた場合、
マナオを攻撃してくるだろう。
言い換えれば、マナオは自分を攻撃してくるモンスターに遭遇したとき、
そのモンスターをマグネタイトで買収しなくてはならない。
攻撃してこないモンスターに遭遇した場合は、
買収して仲魔にする他、ただ通り過ぎる事もできる。

以下のような例で考えてみる。

谷に生息するモンスター
1st... ドラゴン          脅威度 : 8  必要マグネタイト : 1
2nd... ヒドラ            脅威度 : 5  必要マグネタイト : 1
3rd... キラー・ラビット  脅威度 : 10 必要マグネタイト : 2

ドラゴンと遭遇したとき、マナオは1マグネタイトを使って買収するほかない。
なぜなら彼はその時は独りで旅をしており、合計脅威度は0となっているためである。
次に、ヒドラと遭遇したとき、マナオは通り過ぎるか、彼女を買収する事ができる。
最後にキラー・ラビットと遭遇する。もし、マナオがヒドラを仲魔にしていたら、
彼のパーティーの合計脅威度はラビットのそれを上回っており、通り過ぎる事ができる。
そうでなければ、2マグネタイトを使って買収する必要がある。
つまり、最小で2マグネタイトを支払えば谷を通過することができる。

遭遇するモンスターの情報が与えられるので、谷を通過する時の、
支払うマグネタイトの最小を返せ。

制約

1 <= モンスターの数 <= 50
1 <= dread[i] <= 10^12
1 <= price[i] <= 2


考えた事

モンスターの数が50に増えたので、Div2のように全探索は無理だな

dp[ i ][ j ] = i番目のモンスターまでで、j円払ったときの、仲魔の最高脅威度
とする。
(ただし、j円払ってi番目のモンスターに遭遇するのが不可能ならば-1とする)

  • 初期化

dp[ 0 ][ 0 ] = 0, dp[ 0 ][ j ] = -1 ( j != 0 )

  • 更新

通り過ぎる事が出来る場合( j >= dread[ i ] )
dp[ i+1 ][ j ] = max( dp[ i+1 ][ j ] , dp[ i ][ j ] )

金を払う場合
dp[ i+1 ][ j+price[ i ] ] = max( dp[ i+1 ][ j+price[ i ] ], dp[ i ][ j ] + dread[ i ] )

  • 結果

モンスターの数をNとした時に、
dp[ N ][ j ] != -1であるような、最も小さい j


ソースコード

// dp[i][j] = i番目のモンスターまでにjゴールド払ったときの最高脅威度
// -1であれば不可能
long long dp[55][105]; 

class MonstersValley {
public:
    int minimumPrice(vector<long long> dread, vector <int> price){

        int n = dread.size();

        // dp初期化
        for( int i = 0; i <= n; i++ ){
            for( int j = 0; j <= 100; j++ ){
                dp[i][j] = -1;
            }
        }
        dp[0][0] = 0;

        // dp更新
        for( int i = 0; i < n; i++ ){
            for( int j = 0; j <= 100; j++ ){
                if( dp[i][j] == -1 ) continue; // 不可能
                // 金を払わずに済みそう
                if( dp[i][j] >= dread[i] ){
                    dp[i+1][j] = max( dp[i+1][j], dp[i][j] );
                }
                // 金を払う
                dp[i+1][j+price[i]] = max( dp[i+1][j+price[i]], dp[i][j] + dread[i] );
            }
        }

        // 集計
        int res = 10000;
        for( int j = 0; j <= 100; j++ ){
            if( dp[n][j] != -1 ){
                res = j;
                break;
            }
        }

        return res;
    }
};