HDU1069 最长上升子序列

emm。。。。矩形嵌套 还记得吗。。。。就是它。。。

直接贴代码了。。。。

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.Comparator;

import java.util.Scanner;

public class Main{

    final static int maxn = 1000000;

    final static int INF = 0xfffffff;

    public static class node{

        int x,y,h;

        node(int x,int y,int h)

        {

            this.x = x;

            this.y = y;

            this.h = h;

        }

    }

    public static void main(String[] args)  {

        Scanner cin = new Scanner(System.in);

        int cnt = 0;

        while(cin.hasNext())

        {

            ArrayList<node> Node = new ArrayList<>();

            int[] list = new int[maxn];

            int n = cin.nextInt();

            if(n == 0)

                break;

            for(int i=0;i<n;i++)

            {

                list[0] = cin.nextInt();

                list[1] = cin.nextInt();

                list[2] = cin.nextInt();

                Arrays.sort(list,0,3);

                Node.add(new node(list[0],list[1],list[2]));

                Node.add(new node(list[0],list[2],list[1]));

                Node.add(new node(list[1],list[2],list[0]));

            }

            Collections.sort(Node,new Comparator<node>() {

                public int compare(node a,node b)

                {

                    return a.x -b.x;

                }

            });

            int maxx = -INF;

            int[] dp = new int[maxn];

            for(int i=0;i<Node.size();i++)

            {

                dp[i] = Node.get(i).h;

                for(int j=0;j<i;j++)

                {

                    if(Node.get(i).x > Node.get(j).x && Node.get(i).y > Node.get(j).y && dp[j]+Node.get(i).h > dp[i])

                        dp[i] = dp[j] + Node.get(i).h;

                }

                maxx = Math.max(maxx, dp[i]);

            }

            System.out.println("Case " + ++cnt + ": maximum height = " + maxx);

        }

    }

}