const int H = 50; const int W = 50; int t[H][W][H][W]; bool rect[H][W][H][W]; int rec(int a, int b, int c, int d) { if( a > c || b > d )return 0; if( t[a][b][c][d] != -1 )return t[a][b][c][d]; int mx = 0; mx = max( mx, rec(a+1, b, c, d) ); mx = max( mx, rec(a, b+1, c, d) ); mx = max( mx, rec(a, b, c-1, d) ); mx = max( mx, rec(a, b, c, d-1) ); if( rect[a][b][c][d] ){ mx = max( mx, rec(a+1, b+1, c-1, d-1) + 1 ); } return t[a][b][c][d] = mx; } class DonutsOnTheGridEasy { public: int calc(vector <string> g) { const int h = g.size(); const int w = g[0].size(); fill( &t[0][0][0][0], &t[H-1][W-1][H-1][W], -1 ); fill( &rect[0][0][0][0], &rect[H-1][W-1][H-1][W], false ); for(int i=0; i<h; ++i){ for(int j=0; j<w; ++j){ for(int k=i+2; k<h; ++k){ for(int l=j+2; l<w; ++l){ bool flg = true; for(int m=i; m<=k && flg; ++m){ flg = g[m][j] == '0' && g[m][l] == '0'; } if( !flg )continue; for(int m=j; m<=l && flg; ++m){ flg = g[i][m] == '0' && g[k][m] == '0'; } if( !flg )continue; //cout << i << ' ' << j << " : " << k << ' ' << l << endl; rect[i][j][k][l] = true; } } } } return rec(0, 0, h-1, w-1); } };
7/12/2011
SRM455 Div1 Easy
ある長方形の領域中の解は、周囲の4辺の1つを切り落としたモノの最大値 or 4辺全てを切り落としたモノ+1
登録:
コメントの投稿
(
Atom
)
0 件のコメント :
コメントを投稿