動的計画法練習 その2

最大正方形 | 動的計画法 | Aizu Online Judge
* 隣接する三点の dp 結果だけで現在の地点を含む最大正方形の幅がわかってしまう。
* ALGORITHM NOTE 最大正方形の面積 正方形探索を参照した。

class max_square {
public:
    // O(H*W)
    void solve(void) {
        int H, W;
        cin>>H>>W;
        // dp[i][j] := [0,i)x[0,j) 区間内に含まれる最大正方形の幅
        //
        //      X
        //   ABBBX      A : 4x4
        //  XABBCC      B : 3x3
        //   ABBCC      C : 2x2
        //   AAAA?
        //
        //      X
        //   ABBBX     ? = min{2,3,4}
        //  XABBCC
        //   ABB32
        //   AAA4?
        //
        // dp[i][j] は隣接する (i,j-1) (i-1,j) (i-1,j-1) での計算結果からわかる
        vector<vector<int>> dp(H+1, vector<int>(W+1,0));

        // dp の定義より左端一列と一番上一行は 0 となる(ため index は 1 から開始)
        FOR(i, 1, H+1)
        FOR(j, 1, W+1)
        {
            int t;
            cin>>t;
            if (t == 0)
                dp[i][j] = 1;
        }

        int maxWidth = 0;
        FOR(i, 1, H+1)
        FOR(j, 1, W+1)
        {
            if (!dp[i][j])
                continue;
            dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]})+1;
            maxWidth = max(maxWidth, dp[i][j]);
        }
        cout<<maxWidth*maxWidth<<endl;
    }
};

最大長方形 | 動的計画法 | Aizu Online Judge
* 上の問題の長方形板。縦方向の長さを計算しておいて largest rectangle in histogram に帰着させる。
* ALGORITHM NOTE 長方形探索： 最大長方形の面積 Largest Rectangle を参照にした。

class max_rectangle {
public:
    //
    // Largest Rectangle in Histogram のアルゴリズムを応用する
    //
    void solve(void) {
        int H, W;
        cin>>H>>W;

        // 上に向かってきれいなタイルが連続する長さを格納する
        //  . X . X     1 0 1 0
        //  . . . . ->  2 1 2 1
        //  X . . .     0 2 3 2
        vector<vector<int>> seq(H, vector<int>(W,0));
        REP(i, H)
        REP(j, W)
        {
            int t;
            cin>>t;
            if (i == 0)
            {
                if (t == 0)
                    seq[i][j] = 1;
            }
            else
            {
                if (t == 0)
                    seq[i][j] = seq[i-1][j]+1;
            }
        }
        int maxArea = 0;
        // 各行を底面として largest rectangle in histogram を解く
        //
        // . . X .     .
        // . X . X     .   .
        // . . . . --> . . . .
        // X . . .
        //
        REP(i, H)
            maxArea = max(maxArea, (int)largestRectInHist(seq[i]));
        cout<<maxArea<<endl;
    }
};

SPOJ.com - Problem HISTOGRA
* 上の問題で使ったアルゴリズム
* スタックにつむときに 2 パターンあるのがポイント

class largest_rectangle_in_histogram {
public:
    // 長方形の始点と終点を回る、素朴な2重ループでは O(N^2) で TLE してしまう。
    // stack を使った O(N) の解法を考える
    ll max_rectangle(const vector<ll> &_hist) {
        vector<ll> hist(_hist);
        stack<pair<int,ll>> st;

        ll maxArea = 0;
        // 最後のグラフも同じように扱いたいので、末尾に高さ 0 のダミーグラフをいれておく
        hist.push_back(0);
        REP(i, hist.size())
        {
            if (st.empty())
                st.emplace(i, hist[i]);
            else if (st.top().second == hist[i]) // 同じ高さが続くなら次へ
                continue;
            else
            {
                int prev = i;
                while ( st.size() && hist[i] < st.top().second )
                {
                    int l;
                    ll  h;
                    tie(l,h) = st.top();
                    st.pop();
                    prev = l;
                    maxArea = max(maxArea, (i-l)*h);
                }
                //
                // 上りで
                //
                //     |
                //   +-+
                //   |/
                // +-+/
                // |A B C
                //
                // B から長方形始まるケースとして (B,hist[B]) を登録するケース
                //
                //   +--+
                //   |  +-+
                // +-+    |
                // |......+-+
                //-+        |
                //  A BC D E
                // E からさかのぼって (A,hist[E]) を登録するケース
                //
                st.emplace(prev, hist[i]);
            }
        }
        return maxArea;
    }
    void solve(void) {
        while (true)
        {
            int N;
            cin>>N;
            if (N == 0)
                break;
            vector<ll> hist;
            REP(i, N)
            {
                ll h;
                cin>>h;
                hist.push_back(h);
            }
            cout<<max_rectangle(hist)<<endl;
        }
    }
};

なんか最後の方は動的計画法っぽくないな。