首页 > 代码库 > zoj 2067 - White Rectangles
zoj 2067 - White Rectangles
题目:一个由‘.’和‘#’组成矩形,统计里面‘.‘组成的矩形的个数。
分析:经典dp。计算之前要做很多预处理。
状态:f(i,j)为,以点(i,j)作为右下角顶点的矩形的个数;
首先,统计每个‘.‘元素,所在行以他为结束标志的连续的‘.‘的长度L(i,j);
然后,从点(i,j)向左上运动,计算对应的高度的矩形个数maxL(i,j,k);
转移:f(i,j)= sum(maxL(i,j,k)) { 其中,0 < k ≤ j };
(maxL(i,j,k)为从k到i的每行以j为结束标志的矩形最大公共长度)。
说明:(2011-11-02 12:25)。
#include <stdio.h> #include <stdlib.h> #include <string.h> char maps[ 105 ][ 105 ]; int line[ 105 ][ 105 ]; int minl[ 105 ][ 105 ]; int rect[ 105 ][ 105 ]; int main() { int n; while ( scanf("%d",&n) != EOF ) { for ( int i = 1 ; i <= n ; ++ i ) scanf("%s",&maps[ i ][ 1 ]); memset( line, 0, sizeof( line ) ); memset( rect, 0, sizeof( rect ) ); for ( int i = 1 ; i <= n ; ++ i ) for ( int j = 1 ; j <= n ; ++ j ) if ( maps[ i ][ j ] == '.' ) line[ i ][ j ] = line[ i ][ j-1 ]+1; for ( int i = 1 ; i <= n ; ++ i ) for ( int j = 1 ; j <= n ; ++ j ) { int minL = line[ i ][ j ]; for ( int k = i ; k >= 1 ; -- k ) { if ( minL > line[ k ][ j ] ) minL = line[ k ][ j ]; if ( !minL ) break; rect[ i ][ j ] += minL; } } int sum = 0; for ( int i = 1 ; i <= n ; ++ i ) for ( int j = 1 ; j <= n ; ++ j ) sum += rect[ i ][ j ]; printf("%d\n",sum); } return 0; }
zoj 2067 - White Rectangles
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。