TopCoder SRM610: MiningGoldEasy

全マスへの移動を考えるのではなく、残っている gold がある箇所と同じ行または列に移動することを考える。そうすると、移動箇所はたかだか 50*50 だけになる。

あとは、「座標」と「日数」で動的計画法を適用すればよい。 \(O(|event|^4) \)

public class MiningGoldEasy {
    int N, M;
    int[] event_i, event_j;

    int?[, ,] memo = new int?[50, 50, 50];

    int GetCost(int row, int col, int eventIndex) {
        return N + M - Math.Abs(event_i[eventIndex] - row) - Math.Abs(event_j[eventIndex] - col);
    }

    int dfs(int rowIndex, int colIndex, int cur = 0) {
        if (cur == event_i.Length)
            return 0;

        var row = event_i[rowIndex];
        var col = event_j[colIndex];

        if (!memo[rowIndex, colIndex, cur].HasValue) {
            int val = 0;
            int cost = GetCost(row, col, cur);
            for (int i = cur; i < event_i.Length; i++) {
                val = Math.Max(val, dfs(i, colIndex, cur + 1) + cost);
                val = Math.Max(val, dfs(rowIndex, i, cur + 1) + cost);
            }

            memo[rowIndex, colIndex, cur] = val;
        }

        return memo[rowIndex, colIndex, cur].Value;
    }

    public int GetMaximumGold(int N, int M, int[] event_i, int[] event_j) {
        this.N = N;
        this.M = M;
        this.event_i = event_i;
        this.event_j = event_j;
        int ans = 0;
        for (int i = 0; i < event_i.Length; i++) {
            for (int j = 0; j < event_j.Length; j++) {
                ans = Math.Max(ans, dfs(i, j));
            }
        }

        return ans;
    }
}