TCO15 Algorithm Round 2C Easy: YetAnotherCardGame

解法

dp(nターン目の時に)(山札の一番上にある数)の最大値を取るようにdpした。

実は山札の一番上の数字さえ覚えておけば、一番上のカード以下のカードは出せないため、どのカードを出したかということを覚えておく必要はない。毎ターン「カードを出す」か「パス」を選ぶゲームだと考えることができる。あとはゲームが必ず2Nターンで終わるということに注意すれば良い。

コード

import java.util.Arrays;

public class YetAnotherCardGame {

	public int maxCards(int[] petr, int[] snuke) {
		Arrays.sort(petr);
		Arrays.sort(snuke);

		int N = snuke.length;
		int[][] dp = new int[2 * N + 1][101];
		for (int i = 0; i < dp.length; i++) {
			Arrays.fill(dp[i], -1);
		}
		dp[0][0] = 0;

		for (int turn = 0; turn < 2 * N; turn++) {
			for (int num = 0; num < 101; num++) {
				if (dp[turn][num] < 0) {
					continue;
				}
				dp[turn + 1][num] = Math.max(dp[turn][num], dp[turn + 1][num]);
				for (int i = 0; i < N; i++) {
					int card = 0;
					if (turn % 2 == 0) {
						card = petr[i];
					} else {
						card = snuke[i];
					}
					if (num < card) {
						dp[turn + 1][card] = Math.max(dp[turn + 1][card],
								dp[turn][num] + 1);
					}
				}
			}
		}

		int ans = 0;
		for (int i = 0; i < 101; i++) {
			ans = Math.max(ans, dp[2 * N][i]);
		}

		return ans;
	}

}