首页 > 专题系列 > Java解POJ > POJ 1609 Tiling Up Blocks [解题报告] Java
2013
11-10

POJ 1609 Tiling Up Blocks [解题报告] Java

Tiling Up Blocks

问题描述 :

Michael The Kid receives an interesting game set from his grandparent as his birthday gift. Inside the game set box, there are n tiling blocks and each block has a form as follows:



Each tiling block is associated with two parameters (l,m), meaning that the upper face of the block is packed with l protruding knobs on the left and m protruding knobs on the middle. Correspondingly, the bottom face of an (l,m)-block is carved with l caving dens on the left and m dens on the middle.

It is easily seen that an (l,m)-block can be tiled upon another (l,m)-block. However,this is not the only way for us to tile up the blocks. Actually, an (l,m)-block can be tiled upon another (l’,m’)-block if and only if l >= l’ and m >= m’.

Now the puzzle that Michael wants to solve is to decide what is the tallest tiling blocks he can make out of the given n blocks within his game box. In other words, you are given a collection of n blocks B = {b1, b2, . . . , bn} and each block bi is associated with two parameters (li,mi). The objective of the problem is to decide the number of tallest tiling blocks made from B.

输入:

Several sets of tiling blocks. The inputs are just a list of integers.For each set of tiling blocks, the first integer n represents the number of blocks within the game box. Following n, there will be n lines specifying parameters of blocks in B; each line contains exactly two integers, representing left and middle parameters of the i-th block, namely, li and mi. In other words, a game box is just a collection of n blocks B = {b1, b2, . . . , bn} and each block bi is associated with two parameters (li,mi).

Note that n can be as large as 10000 and li and mi are in the range from 1 to 100.

An integer n = 0 (zero) signifies the end of input.

输出:

For each set of tiling blocks B, output the number of the tallest tiling blocks can be made out of B. Output a single star ‘*’ to signify the end of

outputs.

样例输入:

3
3 2
1 1
2 3
5
4 2
2 4
3 3
1 1
5 5
0

样例输出:

2
3
*

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
public class Main {
 static final int N = 100+10;
 static int point[][] = new int[N][N],DP[][] = new int[N][N];
 static void init(){
	for(int i=0;i< N;++i) for(int j=0;j< N;++j) point[i][j] = 0;
}

 static int solve(){
	int i,j;
	for(i=0;i< N;++i) DP[0][i] = DP[i][0] = 0;
	for(i=1;i< N;++i) for(j=1;j< N;++j){
		DP[i][j] = Max(DP[i-1][j],DP[i][j-1])+point[i][j];
	}
	return DP[N-1][N-1];
  }

 static int Max(int a,int b){
	return a>b?a:b;
 }

 public static void main(String[]args) throws Exception{
  int i,a,b,n;
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  while(true){
	cin.nextToken();
	n = (int) cin.nval;
	if(n==0){
		System.out.println("*");
		break;
	}else{
		init();
		for(i=0;i< n;++i){
			cin.nextToken();
			a = (int) cin.nval;
			cin.nextToken();
			b = (int) cin.nval;
			++point[a][b];
		}
		System.out.println(solve());
	}
  }
 }
}

  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  2. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!