# Poj Solution 2241

```http://poj.org/problem?id=2241

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {

/**
* @param args
*/
public static void main(String[] args) {

Scanner cin = new Scanner(System.in);

int kase = 0;
while (true) {

int n = cin.nextInt();

if (n == 0) {
break;
}

kase++;

List<T> list = new ArrayList<T>();

for (int i = 1; i <= n; i++) {
int x = cin.nextInt();
int y = cin.nextInt();
int z = cin.nextInt();

}

Collections.sort(list, new Comparator() {

public int compare(Object arg0, Object arg1) {
T t1 = (T) arg0;
T t2 = (T) arg1;

if (t2.x > t1.x) {
return t2.x - t1.x;
} else if (t2.x == t1.x && t2.y > t1.y) {
return t2.y - t1.y;
} else if (t2.x == t1.x && t2.y == t1.y && t2.z > t1.z) {
return t2.z - t1.z;
}

return -1;
}
});

int[] f = new int[list.size() + 1];
for (int i = 0; i < f.length; i++) {
f[i] = 0;
}

f[0] = list.get(0).z;

int max = f[0];

for (int i = 1; i < list.size(); i++) {
int m = list.get(i).z;

for (int k = 0; k < i; k++) {

if (list.get(k).x > list.get(i).x && list.get(k).y > list.get(i).y) {
m = Math.max(m, f[k] + list.get(i).z);
}
}

max = Math.max(max, m);

f[i] = m;
}
System.out.println("Case " + kase + ": maximum height = " + max);
}
}

static class T {

int x;
int y;
int z;

public T(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
}

}

```
This entry was posted in poj. Bookmark the permalink.