https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0363?year=2017
前提知識
考察過程
1. 横幅4mというのが重要に見える
2. 今回は荷物が置かれているかどうかというのが重要なので、bitdpできそう
3. 丁度1つ上の行の状態だけ持てばいいのでbitdpで確定かな?
4. O(H2^8)も大丈夫そうですね
解法
https://onlinejudge.u-aizu.ac.jp/solutions/problem/0363/review/3136527/hamayanhamayan/C++14
dp[y][msk] := y行目まで確定していて、y行目の埋まり具合がmskのときに置ける荷物の最大個数
mskは荷物がおけない区間にビットが立っている必要があるので、check関数で使えるmskか確認しよう。
あとは荷物を置いていくだけだが、注意点が1行に2つ置く場合の遷移をしっかり用意することである。
(親切にもサンプルにある)
int H, N; int ng[10101][4]; int dp[10101][1 << 4]; //--------------------------------------------------------------------------------------------------- int check(int y, int msk) { rep(x, 0, 4) if (ng[y][x]) if (!(msk & (1 << x))) return 0; return 1; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> H >> N; rep(i, 0, N) { int x, y; cin >> x >> y; ng[y][x] = 1; } rep(y, 0, H - 1) rep(msk, 0, 1 << 4) if(check(y, msk)) { rep(msk2, 0, 1 << 4) if (check(y + 1, msk2)) { // 1個置く rep(x, 0, 3) { if (msk & (1 << x)) continue; if (msk & (1 << (x+1))) continue; if (msk2 & (1 << x)) continue; if (msk2 & (1 << (x + 1))) continue; chmax(dp[y + 1][msk2 + (1 << x) + (1 << (x + 1))], dp[y][msk] + 1); } // 2個置く if (msk == 0 and msk2 == 0) chmax(dp[y + 1][(1 << 4) - 1], dp[y][0] + 2); chmax(dp[y + 1][msk2], dp[y][msk]); } } int ans = 0; rep(msk, 0, 1 << 4) if (check(H - 1, msk)) chmax(ans, dp[H - 1][msk]); cout << ans << endl; }