SRM667 Div2 hard

初めてDiv2 hardを解きました。うれしい。
レートも爆上がり（1194 -> 1323 (+129) ）。とてもうれしい。
これでDiv1に5回くらい残留できるだろうか。
とりあえずmedは死んで、どうぞ。

TopCoder Statistics - Problem Archive
TopCoder Statistics - Problem Statement

問題を理解するのに10分、DPで行けんじゃないか、となるとこまで10分、途中で、これ一つ右の建物にいくつ店があるかも関係すんじゃん死んだ、ってなってから解法がひらめくまで3分、みたいな感じでした。
ぐちゃって書いたコードが一発でちゃんと動いたので助かった……。

n, m = 30なので全探索……はむりだわな、両隣しか関係しないからDPで行けるかな……。
となって、最初 dp[その建物の位置][その建物の店舗数] という配列で
dp[i][j] = (0 <= k <= m) における (dp[i - 1][k] + j * (価値関数))のmax
でいこうかと思い、これ価値関数が一つ右の建物の店舗数にも依存すんじゃん忘れてた、ってなった。
が、思いのほかすぐにひらめき、
dp[その建物の位置][その建物の店舗数][一つ右の建物の店舗数] で
dp[i][j][k] = (0 <= l <= m) における (dp[i - 1][l][j] + j * (価値関数))のmax
とした。O(n * m^3) なので 30^4 = 810000 で楽勝で間に合う。

using System;
using System.IO;
using System.Collections.Generic;
using System.Text;
 
public class ShopPositions {
  public int maxProfit(int n, int m, int[] c) {
        var dp = new int[n][][];
        for (int i = 0; i < n; i++)
        {
            dp[i] = new int[m + 1][];
            for (int j = 0; j <= m; j++)
                dp[i][j] = new int[m + 1];
        }
        for (int i = 1; i <= m; i++)
            for (int j = 0; j <= m; j++)
                dp[0][i][j] = i * c[i + j - 1];

        for (int i = 1; i < n; i++)
            for (int j = 0; j <= m; j++)
                for (int k = 0; k <= m; k++)
                    for (int l = 0; l <= m; l++)
                        dp[i][j][k] = Math.Max(dp[i][j][k], dp[i - 1][l][j] + j * c[i * 3 * m + l + j + k - 1]);

        int max = 0;
        for (int i = 0; i <= m; i++)
            max = Math.Max(max, dp[n - 1][i][0]);

    return max;
  }
}
// Powered by Greed 2.0-RC