Meng

UVA 437 - The Tower of Babylon

Example Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the whole story: The babylonians had n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (xi, yi, zi). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height. They wanted to construct the tallest tower possible by stacking blocks. The problem was that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block. This meant, for example, that blocks oriented to have equal-sized bases couldn’t be stacked. Your job is to write a program that determines the height of the tallest tower the babylonians can build with a given set of blocks. n is less than 30.

Sample input
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0
Sample Output
Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342

题意：这道题是说给一堆箱子，每个箱子可以无限重复用，求出堆起来最高的高度是多少。 能堆起来的规则是，上面的箱子长宽要严格小于下面的箱子。 这道题咋一看，感觉没有什么思路，但是因为箱子可以重复使用，那么一个箱子就可以有三种放法，我都都加入数组之中，并且按底部的面积大小进行排序。 此时题目就变成了最长上升子序列了。 只是这里并不是比较数值的大小，而是比较箱子是否能够放在之前的箱子上。

代码

import java.io.*;  
import java.util.*;  
class box implements Comparable<box>{  
    int x,y,z;  
    public box(int x, int y, int z){  
        this.x = x;
        this.y = y;
        this.z = z;  
    }  
    @Override  
    public int compareTo(box t) {  
        if(t.x * t.y == x * y) return t.z - z;  
        return t.x * t.y - x * y;  
        }  
    }  
public class Main {  
    public static void main (String [] args) throws Exception {  
        Scanner scan = new Scanner(System.in);  
        int count = 1;  
        while(true){  
            int num = scan.nextInt();  
            if(num==0) return;  
            box[] arr = new box[num*3];  
            for(int i= 0;i<num;i++){  
                int x = scan.nextInt();  
                int y = scan.nextInt();  
                int z = scan.nextInt();  
                arr[i*3] = new box(x,y,z);  
                arr[i*3+1] = new box(y,z,x);  
                arr[i*3+2] = new box(x,z,y);  
            }  
            Arrays.sort(arr);  
            int dp[] = new int[100];  
            int max = -1;  
            dp[0] = arr[0].z;  
            for(int i = 1;i < arr.length; i++){  
                dp[i] = arr[i].z;  
                for(int j = 0;j < i; j++){  
                    if((arr[i].x< arr[j].x && arr[i].y < arr[j].y)||(arr[i].x < arr[j].y && arr[i].y < arr[j].x)){  
                        dp[i] = Math.max(dp[i], dp[j]+arr[i].z);  
                    }  
                }  
                max = Math.max(max,dp[i]);  
            }  
            System.out.println("Case "+count+": maximum height = " + max);  
            count++;  
        }  
    }  
}

代码引于 https://www.geek-share.com/detail/2578365500.html

Search

    Table of Contents