Tamflexの貯蔵庫

やる気のない備忘録

aoj DPL_3_B

最大長方形 | 動的計画法 | Aizu Online Judge

最大長方形を求めさせる問題.

こちらを参考に応用する.
ヒストグラムの中の最大長方形を求める問題はlog(n)のオーダで求まる.
あとはそれを行について行えばいいので計算量はlog(w*h)のオーダーで行ける.

struct Rect {int h; int pos;};

int solve(vector<int> v)
{
  stack<Rect> S;
  v.push_back(0);
  int ans = 0;
  FOR(i,0,v.size())
  {
    Rect rect;
    rect.h = v[i];
    rect.pos = i;
    if(S.empty()) S.push(rect);
    else
    {
      if(S.top().h < rect.h) S.push(rect);
      else if(S.top().h > rect.h)
      {
        int t = i;
        while(!S.empty() && S.top().h >= rect.h)
        {
          Rect pre = S.top(); S.pop();
          int area = pre.h * (i-pre.pos);
          ans = max(ans,area);
          t = pre.pos;
        }
        rect.pos = t;
        S.push(rect);
      }
    }
  }
  return ans;
}

int main()
{
  int ans = 0;
  int h,w; cin>>h>>w;
  vector<vector<int> > T(h,vector<int>(w,0));
  vector<vector<int> > U(h,vector<int>(w,0));
  REP(i,h) REP(j,w)
  {
    int t; cin >> t;
    T[i][j] = (t+1)%2;
  }
  REP(i,w) U[0][i] = T[0][i];
  FOR(i,1,h-1) REP(j,w) U[i][j] = T[i][j] ? U[i-1][j]+1 : 0;
  REP(i,h) ans = max(ans,solve(U[i]));
  cout << ans << endl;
  return 0;
}