首页 > 专题系列 > Java解POJ > POJ 2392 Space Elevator [解题报告] Java
2013
11-11

POJ 2392 Space Elevator [解题报告] Java

Space Elevator

问题描述 :

The cows are going to space! They plan to achieve orbit by building a sort of space elevator: a giant tower of blocks. They have K (1 <= K <= 400) different types of blocks with which to build the tower. Each block of type i has height h_i (1 <= h_i <= 100) and is available in quantity c_i (1 <= c_i <= 10). Due to possible damage caused by cosmic rays, no part of a block of type i can exceed a maximum altitude a_i (1 <= a_i <= 40000).

Help the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules.

输入:

* Line 1: A single integer, K

* Lines 2..K+1: Each line contains three space-separated integers: h_i, a_i, and c_i. Line i+1 describes block type i.

输出:

* Line 1: A single integer H, the maximum height of a tower that can be built

样例输入:

3
7 40 3
5 23 8
2 52 6

样例输出:

48

温馨提示:

OUTPUT DETAILS:

From the bottom: 3 blocks of type 2, below 3 of type 1, below 6 of type 3. Stacking 4 blocks of type 2 and 3 of type 1 is not legal, since the top of the last type 1 block would exceed height 40.

解题代码:

//* @author: 
import java.util.Scanner;
import java.util.Arrays;
public class Main{
  private int k;
  private Block block[];
  private boolean access[]=new boolean[400001];

   public Main(int k,Block block[]){
    this.k=k;
    this.block=block;
  }

  private int doIt(){
   int maxs=0;
   access[0]=true;
   Arrays.sort(block);
   for(int i=0;i< k;i++)
    {
       int t=0;
       int tmp=maxs;
       for(int j=maxs;j>=t;j--)
       {
          if(access[j])
           for(int h=1;h<=block[i].c;h++)
           {
                  int x=h*block[i].h+j;
                  if(x>block[i].a) break;
                  if(tmp< x) tmp=x;
                  access[x]=true;        
           }      
       }
       maxs=tmp;
    }
    return maxs;
   }

   public static void main(String args[]){
     Scanner sc=new Scanner(System.in);
     int k=sc.nextInt();
     Block b[]=new Block[k];
     for(int i=0;i< k;i++){
       b[i]=new Block();
       b[i].h=sc.nextInt();
       b[i].a=sc.nextInt();
       b[i].c=sc.nextInt();
     }
     Main m=new Main(k,b);
     System.out.println(m.doIt());
   }
}

class Block implements Comparable{//石头类型
  int h;//石头的高度
  int a;//最大建造高度
  int c;//这种石头的数量

  public Block(){
    h=0;
    a=0;
    c=0;
  }

  public Block(int h,int a,int c){
     this.h=h;
     this.a=a;
     this.c=c;
  }

   public int compareTo(Object o){ 
        Block bl = (Block)o; 
        return (int)(this.a - bl.a); 
    } 

   
 public String toString(){ 
        return "( "+ h +"-"+ a +"-"+c +" )"; 
    } 
 }

  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮