2013
11-11

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)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮