Beyond the Void
BYVoid
pku 1548 Robots
本文正體字版由OpenCC轉換

這是一個二維的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;
}

上次修改時間 2017-02-03

相關日誌