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