此题是zoj1985的变种。

1985的每个小矩形没有宽度w，只有高度h。故加入计算从第x₁到第x_n个矩形的w总和。对于每个小矩形i，求以其为最小基准左右能到达的位置，然后计算总面积。

其中cqf用迭代求左右两侧最多能到达矩形的方法尤为经典。

#include <cstdio>
#include <string>

typedef struct
{
 int w, h;
} Rect;

Rect a[50001];

int n, l[50001], r[50001], s[50001];

void pt ( int i )
{
 printf ( "l%d r%d s%d h%d\n", l[i], r[i], s[r[i] + 1] - s[l[i]] , a[i].h);
}

int main ()
{
 //freopen ( "in.txt", "r", stdin );
 while  ( scanf ( "%d", &n ) && n != -1 )
 {
  int i, ii, sum = 0;
  s[0] = 0;
  for ( i = 0; i < n; i ++ )
  {
   scanf ( "%d %d", &a[i].w, &a[i].h );
   sum += a[i].w;
   s[i + 1] = sum;
  }
  for ( i = 0; i < n; i ++ )
  {
   ii = i;
   while ( ii > 0 && a[i].h <= a[ii - 1].h)
   {
    ii = l[ii - 1];
   }
   l[i] = ii;
  }
  for ( i = n - 1; i >= 0; i -- )
  {
   ii = i;
   while ( ii < n - 1 && a[i].h <= a[ii + 1].h )
   {
    ii = r[ii + 1];
   }
   r[i] = ii;
  }
  int mx = 0, t;
  for ( i = 0; i < n; i ++ )
  {
   //pt ( i );
   t = a[i].h * ( s[r[i] + 1] - s[l[i]] );
   if ( t > mx )
    mx = t;
  }
  printf ( "%d\n", mx );
 }

 return 0;
}

评论