D - 金塊ゲーム AtCoder Beginner Contest 008

問題概略

盤面に金塊が並べてある。
また、回収装置がいくつか置いてあり上下左右の自分から連続した金塊を回収することが出来る。
好きな順番で回収装置を作動させる時、最大の金塊回収数を求めよ。

制約
W,H<10^6
回収装置N <= 30;

解法
回収装置を使うと4つの小さい盤面に分かれて、小さい盤面の中でまた次の回収作業が行われていく。
ここで、盤面が同じならその中での最大値は独立しており、一定である。
よってメモ化再帰が使える。
メモ化再帰なら任意の順番の方法をまとめ上げられるのですごい。
Nは少ないので上下左右の位置をmapにメモできる。

public static void solve() {
        //longを忘れるなオーバーフローするぞ
        W = ni();
        H = ni();
        N = ni();
        p = npad(N);
        memo =new HashMap<>();
        System.out.println(rec(0, H, 0, W));
    }

    //半開区間
    public static long rec(int t, int b, int l, int r) {
        String key = t + "_" + b + "_" + l + "_" + r;
        if (memo.containsKey(key)) return memo.get(key);
        long max = 0;
        for (int i = 0; i < N; i++) {
            int x = p[i].x;
            int y = p[i].y;
            if (l <= x && x < r && t <= y && y < b) {
                long res = 0;
                res += rec(t, y, l, x);//左上
                //左下
                res += rec(y + 1, b, l, x);
                //右上
                res += rec(t, y, x + 1, r);
                //右下
                res += rec(y + 1, b, x + 1, r);
                //十字
                res += b - t + r - l - 1;
                max = Math.max(max, res);
            }
        }
        memo.put(key, max);
        return max;
    }