1. Erste Version: JAVA, [2] + Evgeni Pavlidis


/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu
************************************************/

/**
* ACM programming Contest WS 08/09
* UVa Status: accepted
* Run Time: 0.284
* @author ****
*/

import java.io.*;
import java.util.*;

public class Main {

private static class Box implements Comparable<Box> {
private int dimensions[];
private int index;

public Box(int boxIndex, int boxDimensions[]) {
this.index = boxIndex;
this.dimensions = boxDimensions;
}

public int compareTo(Box otherBox) {
assert this.dimensions.length == otherBox.dimensions.length :
"Compare boxes with the same number of dimensions !";
int rt = 0;
for (int i = 0; i < this.dimensions.length && rt == 0; i++) {
rt = this.dimensions[i] - otherBox.dimensions[i];
}
return rt;
}

public int getIndex() {
return index;
}

public boolean fitIn(Box otherBox) {
assert this.dimensions.length == otherBox.dimensions.length :
"Fit boxes with the same number of dimensions !";
boolean fit = true;
for (int i = 0; fit && i < this.dimensions.length; i++) {
fit = this.dimensions[i] < otherBox.dimensions[i];
}
return fit;
}
}

public static void main(String args[]) {

Scanner scanner = null;
PrintWriter out = null;
try {
scanner = new Scanner(System.in);
out = new PrintWriter(System.out);
while (scanner.hasNextInt()) {
Box boxes[] = new Box[scanner.nextInt()];
int numDimensions = scanner.nextInt();
for (int i = 0; i < boxes.length; i++) {
int boxDimensions[] = new int[numDimensions];
for (int j = 0; j < numDimensions; j++) {
boxDimensions[j] = scanner.nextInt();
}
Arrays.sort(boxDimensions);
boxes[i] = new Box(i, boxDimensions);
}
Arrays.sort(boxes);

int v[] = new int[boxes.length];
Arrays.fill(v, 1);
int vPred[] = new int[boxes.length];
Arrays.fill(vPred, -1);
int indexMax = 0;

for (int i = 1; i < boxes.length; i++) {
Box currBox = boxes[i];
for (int j = 0; j < i; j++) {
if (boxes[j].fitIn(currBox) && v[j] + 1 > v[i]) {
v[i] = v[j] + 1;
vPred[i] = j;
}
}
if (v[i] > v[indexMax]) {
indexMax = i;
}
}

out.println(v[indexMax]);
StringBuilder bf = new StringBuilder();
for (int currIdx = indexMax; currIdx >= 0; currIdx = vPred[currIdx]) {
bf.insert(0, ' ').insert(0, (boxes[currIdx].getIndex() + 1));
}
bf.deleteCharAt(bf.length()-1);
out.println(bf);

}
} catch (Throwable th) {
th.printStackTrace();
} finally {
if (scanner != null) {
scanner.close();
}
if (out != null) {
out.close();
}
}
}
}

2.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 103 - Stacking Boxes
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39
*
* @author Dennis Wilfert
* @version 1.0, 12/17/2009
*
* Methode: Größte aufsteigende Teilfolge
* Status : Accepted
* Runtime: 0.160
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));
StringTokenizer token;
StringBuilder output;

String line = reader.readLine();
int dimensions, boxes, i, j, k, max;
int[][] box;
int[] temp, sequenzes, position;

while (line != null) {

token = new StringTokenizer(line);

boxes = Integer.parseInt(token.nextToken());
dimensions = Integer.parseInt(token.nextToken());
box = new int[boxes][dimensions + 1];
sequenzes = new int[boxes];

// Alle Boxen einlesen
for (i = 0; i < boxes; i++) {
token = new StringTokenizer(reader.readLine());
box[i][dimensions] = i;
for (j = 0; j < dimensions; j++) {
box[i][j] = Integer.parseInt(token.nextToken());
}
// Bei den jeweiligen Boxen die Werte der Dimensionen mit Quicksort aufsteigend sortieren
sort(box[i], 0, dimensions - 1);
}

// Mit Selection-Sort die Boxen aufsteigend sortieren, sodass sie ineinander passen
for (i = 0; i < boxes; i++) {
k = i;
for (j = i + 1; j < boxes; j++) {
if (isBigger(box[k], box[j], dimensions)) {
k = j;
}
}
// Werte tauschen
temp = box[k];
box[k] = box[i];
box[i] = temp;
}

position = new int[boxes];

// Aufsteigende Teilfolgen suchen
max = 0;
for (i = 0; i < boxes; i++) {
for (j = i+1; j < boxes; j++) {
if (sequenzes[j] < sequenzes[i] + 1 && isBigger(box[j], box[i], dimensions)) {
sequenzes[j] = sequenzes[i] + 1;
position[j] = i+1;
}
}
}

for(i = 0; i < boxes; i++){
if(sequenzes[max] < sequenzes[i])
max = i;
}

writer.println(sequenzes[max]+1);

output = new StringBuilder();
// Aus den Positionen in position[] die richtige Reihenfolge aufbauen
while(max >= 0){
output.insert(0, (box[max][dimensions] + 1) + " ");
max = position[max]-1;
}
output.deleteCharAt(output.length()-1);

writer.println(output);


line = reader.readLine();writer.flush();
}

}

static void sort(int[] a, int start, int end) {
int tmp;
int i = start;
int j = end;
int x = a[(start + end) / 2];

do {
// Vom Startpunkt aus einen Wert suchen der >= x ist
while (a[i] < x) {
i++;
}
// Vom Endpunkt aus einen Wert suchen der <= x ist
while (a[j] > x) {
j--;
}

// a[i] und a[j] tauschen
if (i <= j) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
} while (i <= j);

if (start < j) {
sort(a, start, j);
}

if (i < end) {
sort(a, i, end);
}
}

/*
* Feststellen ob alle Elemente in a größer als b sind
*/
static boolean isBigger(int[] a, int[] b, int length) {

for (int i = 0; i < length; i++) {
if (a[i] <= b[i]) {
return false;
}
}

return true;
}
}