PCK17-3

一覧・参加感想記事

問題公式PDF
AOJ

1-5問目
6問目
7問目←ここ

これは解説なのか？

7:積み荷の配置

これ本番中にできなかったの悔しいな…と思いつつ結構考慮しなければいけないケースが多くて実装時間かかった

bitDPですね。
蟻本にもタイル敷き詰めの問題がありましたが、
タイル敷き詰めを見たらbitDPだと思えるようになっておこうね（思っただけで終わった僕のようにならないように実装練習しようね）

解法

1行ずつ見ていく。
ある行を見ているとき、2行上は気にしなくていいね。
よって、横4マスのうち左3マスに左上が置かれているか、という情報を保持する。
状態数は1行に2^3 = 8個、1e4行で8e4通りなので十分間に合う。

ちょっと、そのうちちゃんとした図解作りかも知れないし作らないかもしれない。

英語間違ってるかも（弱）。

#include <iostream>
#include <algorithm>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define RREP(i,n) RFOR(i,0,n)

int bitcount[] = {0,1,1,2,1,2,2,3};

int h,n;
bool b[4][10000];
int dp[2][1<<3];

int main(){
    cin >> h >> n;
    REP(i, n){
        int x,y;
        cin >> x >> y;
        b[x][y] = true;
    }
    REP(y, h-1){
        int *prev = dp[0];
        int *now = dp[1];
        REP(i, 1 << 3){
            now[i] = 0;
            REP(j, 1 << 3){
                bool flag = false;

                // check i(y) height block
                REP(x, 3)REP(dx, 2)REP(dy, 2)
                    if((i & (1 << x)) && b[x + dx][y + dy])
                        flag = true;

                // check j(y-1) height block
                if(y>=1)REP(x, 3)REP(dx, 2)REP(dy, 2)
                    if((j & (1 << x)) && b[x + dx][y - 1 + dy])
                        flag = true;

                // check hit i and j
                REP(x, 2)REP(dxi, 2)REP(dxj, 2)
                    if((i & (1 << (x + dxi))) && (j & (1 << (x + dxj))))
                        flag = true;

                // check in only i and in only j
                REP(x, 2)if((i & (1 << (x + 1))) && (i & (1 << x)))
                    flag = true;
                REP(x, 2)if((j & (1 << x)) && (j & (1 << (x + 1))))
                    flag = true;

                if(flag)continue;
                now[i] = max(now[i], prev[j] + bitcount[i]);
            }
        }
        swap(dp[0], dp[1]);
    }
    int ans = 0;
    REP(i, 1<<3)
        ans = max(ans, dp[0][i]);
    cout << ans << endl;
}

---

6,7問目、微妙に他の方の解より遅いのが気になる(0.01secくらい)がサボり実装のせいだろうか。
実装速度こそ正義だよ。（待って。）
メモリはヒープ使うほうが早いのか？（C++5000兆わからない）

雑ですね。

理解すると理解していなかった頃の感覚がわからなくなるほうではないと思うんだけど、単に書くのがめんどい←