TopCoder SRM 563 Div1 Medium SpellCards

さてSRM563。こちらは本番にどうにもならなかった問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12329

左右に並ぶN枚のカード列からカードを選択すると、そのカードからLevel枚数分右に続くカードを消し、カード規定のダメージを与える。
カードはループ状にグルグル回して選択位置を決められるので、最大のダメージを答える場合を答える。

カードを使う順番が規定されていないので、端から順に使うDPも使えず、しかもループ構造でどうしていいか迷った。
そこでEditorialを参考に解く。

今回はDiv2 HardはDiv1 Mediumの制限が強い版なので、まずそちらを解く。
Div2 Hardではカードがループしないのでちょっと楽。

この場合、カードの左側からカードを取る・とらないの２パターンを１枚ずつ再帰的に選択すればよい。
ただ、カードを取る場合、即座にLevel分のカードを減らすわけではなく、減らすカード数を伝搬させて次のカードに再帰していく。
最終的に減らす分のカード数がNに足りる場合の最大値を求めればよい。
以下のコードでは、カードを左から順に取っているように見えて、実際は再帰表現で右から順に選択していることになる。

Div1の方はループ構造があるが、これは最初に１回N通り回したケースについてDiv2同様に判定すればよい。
というのも、ゲーム中減らすカードが２周ループすることはない（減らすカードが１周分のNより多いわけはない）ためである。
以下のコードでは、FOR(i,N)をFOR(i,1)にすればDiv2 Easyに回答できる。

class SpellCards {
	public:
	int N;
	vector<int> lev;
	vector<int> dam;
	int memo[60][60];
	
	int calc(int cur,int torem) {
		int& res = memo[cur][torem];
		if(cur>=N) return 0;
		if(res!=-1) return res;
		
		// カードを取らない
		res = max(res, calc(cur+1, max(0, torem-1)));
		// カードを取る
		if(cur+(lev[cur]-1)+torem<N) res = max(res, dam[cur]+calc(cur+1, torem+lev[cur]-1));
		return res;
	}
	
	int maxDamage(vector <int> level, vector <int> damage) {
		int res=0;
		int i,j;
		N=level.size();
		lev.resize(N);
		dam.resize(N);
		
		FOR(i,N) {
			FOR(j,N) lev[j]=level[(j+i)%N], dam[j]=damage[(j+i)%N];
			MINUS(memo);
			res = max(res, calc(0,0));
		}
		return res;
	}

};

*まとめ

減らすカード枚数でDPするのに気付けなかった。
あと、ループ処理は最初に１回だけするのにも気づけなかった。