TopCoder SRM 563 Div1 Medium: SpellCards

問題

TopCoder Statistics - Problem Statement

解法

配列が環状になっている区間のDP。「first枚目からcount枚の連続した区間の中からmustLeave枚取り除かなければならない場合の最高点」を考える。

コード

Petrのコードを参考にした。

import java.util.Arrays;

public class SpellCards {
    int[] level;
    int[] damage;
    int[][][] cache;
    int N;

    public int maxDamage(int[] level, int[] damage) {
	N = level.length;
	this.level = level;
	this.damage = damage;
	for (int i = 0; i < N; ++i)
	    --level[i];

	cache = new int[N][N][N];
	for (int[][] a : cache)
	    for (int[] b : a)
		Arrays.fill(b, -1);

	int ans = 0;
	for (int lastPlayCard = 0; lastPlayCard < N; ++lastPlayCard) {
	    int first = (lastPlayCard + 1) % N;
	    int max = dfs(first, N - 1, level[lastPlayCard]);
	    if (max >= 0) {
		ans = Math.max(ans, max + damage[lastPlayCard]);
	    }
	}
	return ans;
    }

    // firstからcount枚の区間からmustLeave枚取り除かなければならない時の最高スコアを返す
    private int dfs(int first, int count, int mustLeave) {
	if (mustLeave > count)
	    return -1;
	if (cache[first][count][mustLeave] >= 0)
	    return cache[first][count][mustLeave];

	int res = 0;
	for (int headCount = 0; headCount < count; ++headCount) {
	    // curのカードを使うことを考える
	    int cur = (first + headCount) % N;
	    int tailCount = count - 1 - headCount;// curの後ろにあるカードの枚数

	    if (level[cur] > tailCount)
		continue;

	    for (int leave = level[cur]; leave <= tailCount; ++leave) {
		int restLeave = mustLeave + level[cur] - leave;
		if (restLeave < 0)
		    break;

		// curより後ろの区間
		int nextFirst = (first + headCount + 1) % N;
		int tailMax = dfs(nextFirst, tailCount, leave);
		if (tailMax < 0)
		    continue;

		// curよりも前の区間
		int headMax = dfs(first, headCount, restLeave);
		if (headMax < 0)
		    continue;

		res = Math.max(res, headMax + tailMax + damage[cur]);
	    }
	}
	cache[first][count][mustLeave] = res;
	return res;
    }
}