This post is written in Chinese. Please consider using Google Translate

这是一个二维的LIS问题，先把第一维排序离散化，把第二维的值存到线性表A中。接下来就是求路径划分了，根据Dilworth定理，最长反链长度等于最小链划分数，所以只需求最长下降序列长度。

由于数值范围有限，可以用计数排序+基数排序，求LIS用二分查找，时间复杂度为O(NlogN)。

另外也可以直接用最小路径覆盖解决。

/* 
 * Problem: pku1548 Robots
 * Author: Guo Jiabao
 * Time: 2009.4.8 21:45
 * State: Solved
 * Memo: 二维LIS Dilworth定理 基数排序 二分查找
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=601,INF=0x7FFFFFFF;
using namespace std;
struct point
{
    int key[2];
}P[MAXN],Q[MAXN];
int N,Ans,A[MAXN],G[MAXN],C[25],order[MAXN];
void countingsort(int y)
{
    int i;
    memset(C,0,sizeof(C));
    for (i=1;i<=N;i++)
        C[P[i].key[y]]++;
    for (i=1;i<=24;i++)
        C[i]+=C[i-1];
    for (i=N;i>=1;i--)
    {
        order[C[P[i].key[y]]]=i;
        C[P[i].key[y]]--;
    }
    for (i=1;i<=N;i++)
        Q[i]=P[order[i]];
    for (i=1;i<=N;i++)
        P[i]=Q[i];
}
void radixsort()
{
    countingsort(1);
    countingsort(0);
}
inline int binsearch(int v)
{
    int a=0,b=N,m;
    while (a+1<b)
    {
        m=(a+b)>>1;
        if (G[m]<v)
            a=m;
        else
            b=m-1;
    }
    if (G[b]<v)
        a=b;
    return a;
}
void dynamic()
{
    int i,k;
    radixsort();
    A[0]=G[0]=0;
    for (i=1;i<=N;i++)
    {
        A[N-i+1]=P[i].key[1];
        G[i]=INF;
    }
    for (i=1;i<=N;i++)
    {
        k=binsearch(A[i]); //查找小于A[i]的最大G[k]，返回k
        if (A[i] < G[k+1])
            G[k+1]=A[i];
    }
    for (i=N;i>=0;i--)
        if (G[i]!=INF)
        {
            Ans=i;
            break;
        }
}
int main()
{
    int x,y;
    freopen("robots.in","r",stdin);
    freopen("robots.out","w",stdout);
    while (scanf("%d%d",&x,&y),x!=-1 || y!=-1)
    {
        N=Ans=0;
        while (x!=0 || y!=0)
        {
            P[++N].key[0]=x;P[N].key[1]=y;
            scanf("%d%d",&x,&y);
        }
        dynamic();
        printf("%dn",Ans);
    }
    return 0;
}