Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4572 Accepted Submission(s): 1938
2 5 6 R F F F F F F F F F F F R R R F F F F F F F F F F F F F F F 5 5 R R R R R R R R R R R R R R R R R R R R R R R R R
45 0
扫描线的第一个题，题目大意：给出m*n的矩阵，R是不能占用的，F是可占用的，每占用一个F要花费3，问，占用的F组成最大的矩形时的花费
扫描线，从上向下扫描，对于每个数存下，到该点时的矩形的最大高度，矩形的左边，右边，可以通过这个计算矩形的大小，如果该点是R，那么高度是0，否则，高度+1，由该点可到的左边和上一层可到的左边共同决定该点的左边。也就是 p[i][j].l = max( p[i][j].l,p[i-1][j].l )，要求最接近该点的。
这样操作后，每个点储存的都是到给点结束时的最大矩形，找出所有点的最大值就可以了。
在输入是既要判断F 也要判断R,不然一直WA
在杭电这份代码是A的，但是其他的oj就不行了，数据水啊
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
int l , r , k , h ;
} p[1100][1100] ;
void init(int n,int m)
{
int i , j , l , r ;
char ch[10] ;
for(i = 1 ; i <= n ; i++)
{
for(j = 1 ; j <= m ; j++)
{
scanf("%s", ch);
if( ch[0] == 'R' )
p[i][j].k = 0 ;
else if( ch[0] == 'F' )
p[i][j].k = 1 ;
}
for(j = 1 , l = 1 ; j <= m ; j++)
{
if( p[i][j].k == 0 )
{
p[i][j].l = -1 ;
l = j+1 ;
}
else
p[i][j].l = l ;
}
for(j = m , r = m ; j >= 1 ; j--)
{
if( p[i][j].k == 0 )
{
p[i][j].r = 999999 ;
r = j - 1 ;
}
else
p[i][j].r = r ;
}
}
}
int main()
{
int t , i , j , n , m , l , r , temp , ans ;
char ch ;
scanf("%d", &t);
while(t--)
{
ans = -1 ;
scanf("%d %d", &n, &m);
init(n,m);
for(i = 1 ; i <= m ; i++)
{
if( p[1][i].k == 1 )
p[1][i].h = 1 ;
else
p[1][i].h = 0 ;
temp = p[1][i].h * ( p[1][i].r - p[1][i].l + 1);
if( temp > ans )
ans = temp ;
}
for(i = 2 ; i <= n ; i++)
{
for(j = 1 ; j <= n ; j++)
{
if( p[i][j].k == 0 )
{
p[i][j].h = 0 ;
}
else
{
p[i][j].h = p[i-1][j].h + 1 ;
p[i][j].l = max( p[i][j].l,p[i-1][j].l );
p[i][j].r = min( p[i][j].r,p[i-1][j].r );
}
temp = p[i][j].h * ( p[i][j].r - p[i][j].l + 1 );
if(temp > ans)
ans = temp ;
}
}
printf("%d\n", ans*3);
}
return 0;
}
多加了一个判断是不是m行，每行是不是n个。。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
int l , r , k , h ;
} p[1100][1100] ;
void init(int n,int m)
{
int i , j , l , r , ll , top ;
char str[10000] ;
memset(p,0,sizeof(p));
for(i = 1 ; i <= n ; i++)
{
gets(str);
if( str[0] == '\n' )
break;
ll = strlen(str);
top = 1 ;
for(j = 0 ; j < ll ; j++)
{
if( str[j] == 'F' )
p[i][top++].k = 1 ;
else if( str[j] == 'R' )
p[i][top++].k = 0 ;
}
}
for(i = 1 ; i <= n ; i++)
{
for(j = 1 , l = 1 ; j <= m ; j++)
{
if( p[i][j].k == 0 )
{
p[i][j].l = -1 ;
l = j+1 ;
}
else
p[i][j].l = l ;
}
for(j = m , r = m ; j >= 1 ; j--)
{
if( p[i][j].k == 0 )
{
p[i][j].r = 999999 ;
r = j - 1 ;
}
else
p[i][j].r = r ;
}
}
}
int main()
{
int t , i , j , n , m , l , r , temp , ans ;
char ch ;
scanf("%d", &t);
while(t--)
{
ans = -1 ;
scanf("%d %d ", &n, &m);
init(n,m);
for(i = 1 ; i <= m ; i++)
{
if( p[1][i].k == 1 )
p[1][i].h = 1 ;
else
p[1][i].h = 0 ;
temp = p[1][i].h * ( p[1][i].r - p[1][i].l + 1);
if( temp > ans )
ans = temp ;
}
for(i = 2 ; i <= n ; i++)
{
for(j = 1 ; j <= n ; j++)
{
if( p[i][j].k == 0 )
{
p[i][j].h = 0 ;
}
else
{
p[i][j].h = p[i-1][j].h + 1 ;
p[i][j].l = max( p[i][j].l,p[i-1][j].l );
p[i][j].r = min( p[i][j].r,p[i-1][j].r );
}
temp = p[i][j].h * ( p[i][j].r - p[i][j].l + 1 );
if(temp > ans)
ans = temp ;
}
}
printf("%d\n", ans*3);
}
return 0;
}
hdu1505--City Game(扫描线+坑啊 ),布布扣,bubuko.com
原文：http://blog.csdn.net/winddreams/article/details/38488397