SRM610 Div2 Hard "MiningGoldEasy"

問題

TopCoder Statistics - Problem Statement

訳

あなたはゴブリンの炭鉱労働者である。あなたの仕事は金を掘ることだ。

あなたは鉱山にいる。鉱山は(N+1) * (M+1)のグリッドで表すことができる。縦の行は0からN、横の列は0からMの番号が付けられている。

あなたは今日から数日間この鉱山で仕事をする。初日である今日(day 0)は好きなマスを選んで仕事をすることができる。一日経つごとに、今いるマスに留まるか、同じ列の好きな行に移動するか、同じ行の好きな列に移動することができる。

金を発掘するたびに利益を得ることができる！N + Mから金の場所と今いる場所のマンハッタン距離を引いたものが利益となる。正確には金が(a, b)にあり、あなたが(c, d)にいたとすると、N + M - |a-c| - |b-d|となる。

あなたはint N, Mが与えられる。さらにint[] event_i, event_jが与えられる。これの意味はk日目にマス(event_i[k], event_j[k])で金を発掘したことを表す。

最善の移動方法を行ったときの利益の最大値を返せ。

制約

1 <= N, M <= 10^6
1 <= event_i, event_jの要素数 <= 50

解法

同じ列・同じ行に金が一切ないマスに移動するのは意味がない（らしい）。そう考えると最大でも50 * 50のグリッドを移動することになり、状態の数は何日目・いる場所でN^3となる。更新は縦移動50横移動50の100回となるため、DPするとO(N^4)となり、計算可能となる。

（らしい）の部分が一番大事なんだが・・・うーーむ・・・

ソースコード

int dp[55][55][55];

class MiningGoldEasy {

    public:

    int GetMaximumGold(int N, int M, vector <int> e_i, vector <int> e_j) {
        int D = e_i.size();

        // dp初期化
        memset(dp, 0, sizeof(dp));
        for (int y = 0; y < D; y++) {
            for (int x = 0; x < D; x++) {
                dp[0][y][x] = N + M - abs(e_i[0] - e_i[y]) - abs(e_j[0] - e_j[x]);
            }
        }
        
        // dp更新
        for (int i = 1; i < D; i++) {
            for (int y = 0; y < D; y++) {
                for (int x = 0; x < D; x++) {
                    // move y
                    for (int ny = 0; ny < D; ny++) {
                        dp[i][ny][x] = max(dp[i][ny][x], 
                            dp[i - 1][y][x] + N + M - abs(e_i[i] - e_i[ny]) - abs(e_j[i] - e_j[x]));
                    }
                    // move x
                    for (int nx = 0; nx < D; nx++) {
                        dp[i][y][nx] = max(dp[i][y][nx], 
                            dp[i - 1][y][x] + N + M - abs(e_i[i] - e_i[y]) - abs(e_j[i] - e_j[nx]));
                    }
                }
            }
        }

        // dp集計
        int res = 0;
        for (int y = 0; y < D; y++) {
            for (int x = 0; x < D; x++) {
                res = max(res, dp[D - 1][y][x]);
            }
        }

        return res;
    }
};