SRM565 Div1 Easy - MonstersValley
問題
マナオは一人で旅に出た
道中で出会うモンスターはn匹いて、i番目に出会うモンスターの怖さはd[i]で、仲間にするにはp[i]円かかる
モンスターに出会ったとき、金を払って仲間にするという選択肢が常にある
またはマナオのチームの怖さの合計がそのモンスターの怖さ以上であれば、無視してやり過ごすこともできる
そうでないときはモンスターはマナオを襲う
モンスターに襲われずに旅を終えるために必要な金の最小値を求めよ
1 <= n <= 50
1 <= d[i] <= 10^12
p[i] = 1 or 2
解法
dp[i][j]: i番目のモンスターと遭遇し終えた時点でj円使った場合のチームの怖さの合計の最大値
class MonstersValley { public: int minimumPrice(vector<ll> d, vector<int> p) { ll n = d.size(), dp[55][111] = {}; memset(dp, -1, sizeof(dp)); dp[0][0] = 0; rep(i,n) rep(j,111) if (dp[i][j]!=-1) { chmax(dp[i+1][j+p[i]], dp[i][j] + d[i]); if (d[i]<=dp[i][j]) chmax(dp[i+1][j], dp[i][j]); } rep(i,111) if (dp[n][i]!=-1) return i; return -1; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12350&rd=15187