TopCoder SRM602: TypoCoderDiv1

動的計画法。

rating が 2200 を超えた場合だけ特別処理することで、保持するべき「現在のrating」の状態数を 0～2199 までに落とせる。

public class TypoCoderDiv1 {
    int?[,] memo = new int?[51, 2200];

    public int dfs(int pos, int[] D, int rating) {
        if (pos == D.Length) return 0;
        if (rating >= 2200) {
            if (rating - D[pos] < 2200) {
                return dfs(pos + 1, D, rating - D[pos]) + 1;
            }
            return -1 << 28;
        }
        if (rating < 0) rating = 0;
        if (!memo[pos, rating].HasValue) {
            int val = 0;
            val = Math.Max(val, dfs(pos + 1, D, rating + D[pos]) + ((rating + D[pos]) >= 2200 ? 1 : 0));
            val = Math.Max(val, dfs(pos + 1, D, rating - D[pos]));
            memo[pos, rating] = val;
        }
        return memo[pos, rating].Value;
    }

    public int getmax(int[] D, int X) {
        return dfs(0, D, X);
    }
}

以下のように場合分けを頑張ってもいいが、少し複雑になる。

public class TypoCoderDiv1 {
    int?[,] memo = new int?[55, 3000];

    public int getmax(int[] D, int rate, int pos = 0) {
        if (rate < 0) rate = 0;
        if (pos == D.Length) {
            return 0;
        }
        if (!memo[pos, rate].HasValue) {
            int val = 0;
            if (rate + D[pos] < 2200) {
                val = Math.Max(val, getmax(D, rate + D[pos], pos + 1));
            } else {
                if (pos + 1 < D.Length && rate + D[pos] - D[pos + 1] < 2200) {
                    val = Math.Max(val, getmax(D, rate + D[pos] - D[pos + 1], pos + 2) + 2);
                }
                if (pos + 1 >= D.Length) {
                    val = Math.Max(val, getmax(D, rate + D[pos], pos + 1) + 1);
                }
            }
            val = Math.Max(val, getmax(D, rate - D[pos], pos + 1));

            memo[pos, rate] = val;
        }
        return memo[pos, rate].Value;
    }
}