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