首页 > 专题系列 > Java解POJ > POJ 1038 Bugs Integrated, Inc. [解题报告] Java
2013
11-08

POJ 1038 Bugs Integrated, Inc. [解题报告] Java

Bugs Integrated, Inc.

问题描述 :

Bugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 2*3 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into N*M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.



Finally, the plate of silicon is cut into memory chips. Each chip consists of 2*3 (or 3*2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.

Task

You are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Your task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.

输入:

The first line of the input file consists of a single integer D (1 <= D <= 5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x and y (1 <= x <= N, 1 <= y <= M) ?coordinates of one bad square (the upper left square has coordinates [1, 1], the bottom right is [N,M]).

输出:

For each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate.

样例输入:

2
6 6 5
1 4
4 6
2 2
3 6
6 4
6 5 4
3 3
6 1
6 2
6 4

样例输出:

3
4

解题代码:

//* @author 
import java.util.*;

public class Main {
 static Scanner in = new Scanner(System.in);
 static int[] p = new int[12];
 static {
  p[0] = 1;
  for(int i=1; i!=p.length; ++i)
	p[i] = 3*p[i-1];
  }
  
  static int get(int s, int i) {
	return s/p[i]%3;
  }

  static int set(int s, int i, int v) {
	return s+(v-get(s, i))*p[i];
  }

  public static void main(String[] args) {
   int t = in.nextInt();
   while(t-->0) {
	int n = in.nextInt();
	int m = in.nextInt();
	if(m>10) while(true);
	boolean[][] map = new boolean[n+1][m+1];
	for(int i=0; i<=n; ++i) map[i][m] = true;
	for(int j=0; j<=m; ++j) map[n][j] = true;
	int k = in.nextInt();
	while(k-->0) map[in.nextInt()-1][in.nextInt()-1] = true;
	int[][] dp = new int[m+1][p[m]];
	dp[0][p[m]-1]=1;
	for(int i=0; i!=n; ++i) {
	 for(int j=0; j!=m; ++j) {
	  for(int s=0, _s; s!=p[m]; ++s) {
		int x = dp[j][s];
		if(x==0)continue;
		int l = get(s, j);
		_s = set(s, j, Math.min(2, l+1));
		dp[j+1][_s] = Math.max(dp[j+1][_s], x);
		int r = get(s, j+1);
		if(l!=2||r!=2) continue;
		if(map[i+0][j+0]) continue;
		if(map[i+0][j+1]) continue;
		if(map[i+1][j+0]) continue;
		if(map[i+1][j+1]) continue;
		if(!map[i+2][j]&&!map[i+2][j+1]) {
			_s = set(set(s, j, 0), j+1, 0);
			if(j+2>m)while(true);
			dp[j+2][_s] = Math.max(dp[j+2][_s], x+1);
		}
		if(get(s, j+2)==2&&!map[i][j+2]&&!map[i+1][j+2]) {
			_s = set(set(set(s, j, 1), j+1, 1), j+2, 1);
			if(j+3>m)while(true);
			dp[j+3][_s] = Math.max(dp[j+3][_s], x+1);
		}
	}
       }
	int[] tmp = dp[m];
	for(int j=m; j>=1; --j)
	  Arrays.fill(dp[j] = dp[j-1], 0);
        dp[0] = tmp;
      }
	int ans = 0;
	for(int s=0; s!=p[m]; ++s)
	  ans = Math.max(ans, dp[0][s]);
	System.out.println(ans-1);
  }
 }
}

  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。