TopCoder SRM 563 Div1 Medium SpellCards
問題
n枚のカードが一列に並んでいる。
カードにはlevel, damageが設定されており、i番目のカードのlevelはlevel[i], ダメージはdamage[i]である。
このカードに対して次の操作のどちらかを行う。
1. 先頭のカードを末尾へ移動する。
2. 先頭のカードの右にカードがlevel-1枚以上あるとき、
先頭からlevel枚のカードを順に取り除き、damageの点数を得る。
この操作を、繰り返し何度でも行えるとき、得られる得点の合計の最大値を求めよ。
制約条件
n≦50
level[i]≦50
damage[i]≦10000
方針
1.の操作が行えない場合を考える。
これは、次のようなメモ化再帰でできる。
rec(l, r, x)を[l, r]の範囲のうち、x枚を無駄に捨てるときの場合の数とする。
rec(l, r, x)は、
カードlを2.の操作で使うか、もしくは捨てることができる。
2.の操作で使う場合、カードiまでを2.で捨てるものとすれば、
rec(l, r, x) = max{rec(l + 1, i, level[l] - 1) + rec(i + 1, r, x)}
カードlを捨てる場合、rec(l, r, x) = rec(l + 1, r, x - 1)
以上より漸化式がたったので、メモ化再帰できる。
次に1.の操作が行える場合であるが、これは単にカードをループさせて考えればよいだけ。
1, 2, ..., nのカードの後にまた1, 2, ..., nのカードをくっつけて、
その中でn枚の列を全部考えればいい。
ソースコード
int n; vi L, D; int dp[110][110][60]; int rec(int l, int r, int dis){ if(dis < 0) return -inf; int &res = dp[l][r][dis]; if(res != -1) return res; if(r - l == dis) return res = 0; if(r - l < dis) return res = -inf; res = rec(l + 1, r, dis - 1); for(int i = L[l]; i <= r - l; i++) res = max(res, D[l] + rec(l + 1, l + i, L[l] - 1) + rec(l + i, r, dis)); if(res < 0) res = -inf; return res; } class SpellCards { public: int maxDamage(vector <int> level, vector <int> damage) { n = level.size(); L = level; D = damage; rep(i, n){ L.pb(level[i]); D.pb(damage[i]); } memset(dp, -1, sizeof(dp)); int ans = 0; rep(i, n) rep(j, n + 1) ans = max(ans, rec(i, i + n, j)); return ans; } };