TopCoder SRM 523 Div1 Medium: BricksN
解法
メモ化再帰。「あっ!この問題SRMで見たことある!」感がすごい。
kenkoooo.hatenablog.com
kenkoooo.hatenablog.com
kenkoooo.hatenablog.com
kenkoooo.hatenablog.com
コード
import java.util.Arrays; public class BricksN { private final int MOD = (int) 1e9 + 7; private int H; private long[][] dp; private long[] block; public int countStructures(int w, int h, int k) { this.H = h; // block[i]:= 幅iのブロックの作り方 block = new long[w + 1]; block[0] = 1; for (int i = 0; i < w; i++) { for (int b = 1; b <= k; b++) { if (i + b <= w) { block[i + b] = (block[i + b] + block[i]) % MOD; } } } // dp[h][n]:= 高さhにあるn個の連続した区間の積み方 dp = new long[h + 1][w + 1]; for (int i = 0; i < dp.length; i++) { Arrays.fill(dp[i], -1); } return (int) dfs(0, w); } // メモ化再帰 private long dfs(int h, int n) { if (n == 0) { return 1; } if (h >= H) { return 1; } if (dp[h][n] >= 0) { return dp[h][n]; } dp[h][n] = 0; // 左端に幅kのブロックを置いた時、右の幅n-1-kの部分の積み方も考える for (int k = 0; k <= n; k++) { long tmp = dfs(h + 1, k) * block[k]; tmp %= MOD; if (n - 1 - k >= 0) { tmp *= dfs(h, n - 1 - k); tmp %= MOD; } dp[h][n] += tmp; dp[h][n] %= MOD; } return dp[h][n]; } }