SRM 523 div1 med:BricksN - mayoko’s diary

問題

解法

典型 dp を 2 回やります。

まずひとつ目の dp は,
dp[l][i] = (i 番目までのブロックを使って長さ l のブロックを作る方法は何通りあるか)という dp です。
これは, まず l を i-1 番目以下のブロックを使う場合の dp[l][i-1] 通り, および長さ i のブロックを使う場合を考えれば良いです。後者は, 初めて長さ i のブロックを使う場所がどこかによって場合分けをします。

もうひとつの dp は, dp[h][w] = (高さ h の時点で, 最大幅 w であるようなブロックの積み方は何通りあるか)という dp です。
これも似たような感じで解けます。長さが 1 以上のブロックを初めて置く場所がどこか, その長さはいくつか, の場合分けをして上手くメモ化再帰します。初めて置く場所は座標が大きい順にやると dfs がループすることがないので嬉しいです。

得た知見

前の SRM で出てきた「初めて現れる場所」で場合分けする dp を使えた
dfs の順番気をつければループを防げる発想もなかなか出てこなかった

const int MAX = 55;
const ll MOD = 1e9+7;
ll dp[MAX][MAX];
ll how[MAX];
ll memo[MAX][MAX];
int H;

ll dfs(int h, int w) {
    if (h == H || w <= 0) return how[0];
    ll& ret = memo[h][w];
    if (ret >= 0) return ret;
    ret = how[0];
    for (int i = w-1; i >= 0; i--) {
        for (int l = 1; i+l <= w; l++) {
            int R = w-i-l-1;
            ll plus = dfs(h, R) * how[l] % MOD;
            (plus *= dfs(h+1, l)) %= MOD;
            (ret += plus) %= MOD;
        }
    }
    return ret;
}

class BricksN {
public:
    int countStructures(int w, int h, int k) {
        H = h;
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i <= k; i++) dp[0][i] = 1;
        for (int l = 1; l <= w; l++) {
            for (int i = 1; i <= k; i++) {
                dp[l][i] = dp[l][i-1];
                for (int s = 0; s+i <= l; s++) {
                    int L = s, R = l-s-i;
                    dp[l][i] += dp[L][i-1] * dp[R][i] % MOD;
                    dp[l][i] %= MOD;
                }
            }
        }
        for (int i = 0; i <= w; i++) {
            //cout << i << "  " << dp[i][k] << endl;
            how[i] = dp[i][k];
        }
        memset(memo, -1, sizeof(memo));
        return dfs(0, w);
    }