SRM 610 div 1
easyだけ解きました。
まず横方向に見ていって横に連続したしましまの長さを記録しておく。その後、縦に見ていく。縦に見るときは、次に長方形の幅(横のながさ)が伸びるか縮むかで場合分けをする。
幅が伸びるとき:伸びた長さで高さ1の長方形を追加
幅が縮むとき:以前の長方形で縮んだ長さより長い物は縮める
queueとかで長方形を持っておけばよい
計算量は横n縦mとして、たぶんO(n*m^2)
#include <cstdio> #include <algorithm> #include <string> #include <vector> #include <queue> using namespace std; typedef pair<int,int> P; int a[110][110]; int dp[110][110]; class TheMatrix{ public: int MaxArea(vector <string> board){ int ans=0; int H,W; H=board.size(); W=board[0].size(); for(int i=0;i<H;i++) for(int j=0;j<W;j++) a[i+1][j+1]=board[i][j]; for(int i=1;i<=H;i++) for(int j=1;j<=W;j++) dp[i][j] = ((a[i][j]!=a[i][j-1]) ? dp[i][j-1]+1 : 1); for(int j=1;j<=W;j++){ queue<P> Q; for(int i=1;i<=H;i++){ if(a[i][j] != a[i-1][j]){ queue<P> R; int deepest=0; while(!Q.empty()){ P p = Q.front(); Q.pop(); ans=max(ans,min(dp[i][j],p.first)*(p.second+1)); if(p.first >= dp[i][j]) deepest=max(deepest,p.second); else R.push(P(p.first,p.second+1)); } ans = max(ans,(deepest+1)*dp[i][j]); R.push(P(dp[i][j],deepest+1)); if(dp[i][j-1] > dp[i][j]){ ans = max(ans,dp[i][j]); R.push(P(dp[i][j],1)); } while(!R.empty()){ Q.push(R.front()); R.pop(); } }else{ while(!Q.empty()) Q.pop(); ans = max(ans,dp[i][j]); Q.push(P(dp[i][j],1)); } } } return ans; } };