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();

                list.add(new T(x, y, z));
                list.add(new T(y, x, z));

                list.add(new T(x, z, y));
                list.add(new T(z, x, y));

                list.add(new T(y, z, x));
                list.add(new T(z, y, x));

            }

            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.

Leave a Reply

Your email address will not be published. Required fields are marked *