pku 1548 Robots
这是一个二维的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;
}