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