HDU1069 Monkey and Banana

题目大意

给定 n 种盒子, 每种盒子无限多个, 需要叠起来, 在上面的盒子的长和宽必须严格小于下面盒子的长和宽, 求最高的高度.

思路

对于每个方块, x, y, z 的全排列共有 6 种可能性, 每种可能性只需要一个方块, 因为方块必须严格小于, 若有两个相同的方块, 则不符合题意.

先将方块按照 x, y 依次进行排序

设 dp[i] 为第 i 个方块时的最高高度, 则每个方块的最高高度为 dp[i] = max(dp[j] + arr[i].z). 每次处理 i 时均默认该方块加入叠成的塔中, 对于后面的状态, 可以不选择这个状态.

代码

package 基础DP1;

import java.util.Arrays;

import java.util.Scanner;

class Block implements Comparable<Block>{

	int x, y, z;

	Block(int _x, int _y, int _z) {

		x = _x; y = _y; z = _z;

	}

	@Override

	public int compareTo(Block arg0) {

		if(x != arg0.x)

			return x - arg0.x;

		return y - arg0.y;

	}

}

public class HDU1069 {

	public static void main(String[] args) {

		// TODO Auto-generated method stub

		Scanner in = new Scanner(System.in);

		int round = 0;

		while(true) {

			int nBlock = in.nextInt();

			if(0 == nBlock)

				break;

			Block[] arr = new Block[nBlock * 6 + 1];

			for(int i = 1; i <= nBlock * 6; ) {

				int x = in.nextInt();

				int y = in.nextInt();

				int z = in.nextInt();

				arr[i++] = new Block(x, y, z);

				arr[i++] = new Block(x, z, y);

				arr[i++] = new Block(y, x, z);

				arr[i++] = new Block(y, z, x);

				arr[i++] = new Block(z, y, x);

				arr[i++] = new Block(z, x, y);

			}

			Arrays.sort(arr, 1, arr.length);

			int[] dp = new int[nBlock * 6 + 1];

			int ans = 0;

			for(int i = 1; i <= nBlock * 6; i++) {

//				System.out.println("x is" + arr[i].x + " y is " + arr[i].y + " z is " + arr[i].z);

				int maxHeight = 0;

				for(int j = 1; j < i; j++) {

					if(arr[j].x >= arr[i].x || arr[j].y >= arr[i].y)

						continue;

					maxHeight = Math.max(maxHeight, dp[j]);

				}

				dp[i] = maxHeight + arr[i].z;

				ans = Math.max(ans, dp[i]);

			}

			System.out.printf("Case %d: maximum height = %d", ++round, ans);

			System.out.println();

		}

	}

}

巴特西

HDU1069 Monkey and Banana

HDU1069 Monkey and Banana

题目大意

思路

代码

最新文章

热门文章