学步园

题意：Michael The Kid有n块积木，每块积木左上有l个凸口，右上有w个凸口，左下右l个凹口，右下有w个凹口。当l
>= l'并且m >=
m'时，木块'可安装于另一个上面。问最高能叠几层积木。

思路：这个问题可以转化求最长非递增子序列  以l 降序（l相同 m降序）排列

//228K   
47MS
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define M 10010
using namespace std;

struct data
{
    int
l,m;
}node[M];

bool cmp (data a,data b)
{
    if (a.l
> b.l)
       
return true;
    if (a.l ==
b.l&& a.m >
b.m)
       
return true;
    return
false;
}

int main ()
{
    int
max,n,i,j;
    int
dep[M];               
//dep[i]表示第i块木能堆多高
    while (scanf
("%d",&n)&&n)
    {
       
memset (dep,0,sizeof(dep));
       
for (i = 0;i < n;i ++)
           
scanf
("%d%d",&node[i].l,&node[i].m);

       
sort (node,node + n,cmp);
       
dep[0] = 1;
       
for (i = 0;i < n;i
++)     
//求最长非递增子序列
       
{
           
max = 0;
           
for (j = 0;j < i;j ++)
               
if (node[j].l >=
node[i].l&&node[j].m
>= node[i].m&&dep[j]
>= max)
                   
max = dep[j];
           
dep[i] = max + 1;
       
}
       
max = dep[0];
       
for (i = 1;i < n;i
++)      
//取最大的就是ans
           
max = max > dep[i] ? max : dep[i];
       
printf ("%d\n",max);
    }
    printf
("*\n");
    return
0;
}