toj_2885.cpp

Tianjin University Online Judge 的80多道题目 .

/*2885.   Tetris Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 382   Accepted Runs: 144


You must be very familiar with the game "Tetris". Now we consider a simplified version of this game. In this version, all the blocks are rectangle, and you even can't move the blocks horizontally when they are falling.

Given the description of the blocks series, which contains the horizontal position and the height of each block. You are requested to calculate the maximum height when all the blocks are landed by the given order.

Input
The first line of each test case contains the number of the blocks N and the width of the game arena W. Then N lines following. Each contains three integers Si, Ei, Hi, which means the block's horizontal position is the interval [Si, Ei] and the height of the block is Hi.

You can assume W ≤ 10^9, N ≤ 1000, 1 ≤ Si ≤ Ei ≤ W, 1 ≤ Hi ≤ 1000.

The input is terminated with W = N = 0.

Output
Output one number for each test case, containing the maximum height.

Sample Input

3 10
1 3 2
3 4 5
6 7 6
0 0

Sample Output

7

Hint: The figure below describes the sample case.



Source: TJU Team Selection Contest 6*/

#include<cstdio>
#include<cstring>

int main()
{
  char **map;
  int n , w , blockS , blockE , blockH , blockSH , blockEH , maxH , finalH , i , j , k;
  bool flag;
  maxH = 1000;
  finalH = 0;
  while ( scanf( "%d%d" , &n , &w ) != EOF && n != 0 && w != 0 )
    {
      map = new char * [  maxH + 1 ];
      for ( i = 1; i <= maxH; i++ )
	{
	  map[ i ] = new char [ w + 1 ];
	}
	for ( i = 1; i <= maxH; i++ )
	for ( j = 1; j <= w; j++ )
	map[ i ][ j ] = 0;
       for ( i = 0; i < n; i++ )
	{
	  scanf( "%d%d%d" , &blockS , &blockE , &blockH );
	  flag = false;
	  for ( j = 0; j <= finalH && !flag; j++ )
	    {
	      for ( flag = true , k = blockS ; k < blockE; k++ )
		{
		  if ( map[ j ][ k ] )
		    {
		      flag = false;
		      break;
		    }
		}
	    }
	  blockSH = j;
	  blockEH = j + blockH - 1;
	  if ( blockEH > finalH )
	    finalH = blockEH;
	  for ( j = blockSH ; j <= blockEH ; j++ )
	    {
	      memset( &map[ j ][ blockS ] , 1 , blockE - blockS + 1 );
	    }
	}
      printf( "%d\n" , finalH );
    }
  return 0;
}