hcd.cpp

来自「1RIP路由协议 ——RIP协议最初是为Xerox网络系统的Xeroxpa」· C++ 代码 · 共 55 行

#include <stdio.h>

int los_len(int x[],int n) //最长递减子序列长度
{
	int i,j,dmax,d[1001];
	for(i=1;i<=n;i++)
		d[i]=1;
	for(i=n-1;i>=1;i--)
		for(j=i+1;j<=n;j++)
			if(x[j]<x[i]&&d[i]<d[j]+1)
				d[i]=d[j]+1;
	dmax=0;
	for(i=1;i<=n;i++)
		if(d[i]>dmax)
			dmax=d[i];
	return dmax;
}

int main()
{
	int i,j,n,x[1001],max,a[1001],b[1001],tp1,tp2,max1,max2;
//	freopen("in.txt","r",stdin);
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
			scanf("%d",&x[i]);
		max=0;
		for(i=1;i<=n;i++)
		{
			tp1=0;
			tp2=0;
			for(j=i-1;j>=1;j--)
			{
				if(x[j]<x[i])
					a[++tp1]=x[j];
			}
			for(j=i+1;j<=n;j++)
			{
				if(x[j]<x[i])
					b[++tp2]=x[j];
			}
			if(tp1+tp2<max)
				continue;
			max1=los_len(a,tp1);
			if(tp2+max1<max)
				continue;
			max2=los_len(b,tp2);
			if(max1+max2>max)
				max=max1+max2;
		}
		printf("%d\n",max+1);
	}
	return 0;
}