此题是zoj1985的变种。 1985的每个小矩形没有宽度w，只有高度h。故加入计算从第x1到第xn个矩形的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;} 2251096 2007-03-02 15:10:47 Accepted 2422 C++ 00:00.23 1368K Crux.D

评论