noj 1008 合唱队形 nlogn.txt

一些典型DP题的代码

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

//NOJ 1008 合唱队形 nlogn
//最长递增子序列（注意！！不是不降子序列）
#define NMAX 105
#define MIN -30000
int shuru[NMAX];
int ans[NMAX];
int nixu[NMAX];
int left[NMAX];
int right[NMAX];

int find(int key,int len)
{
	int low,high,mid,max=ans[0];
	low=1;high=len;mid=(low+high)/2;
	while(low<=high)
	{
		if(key<=ans[mid]) high=mid-1;
		//若有shuru=[1 3 1 ?] 到第3位时,有ans=[1 3],注意是<=,这样找出的max是0而不是1
		else
		{
			max=mid;
			low=mid+1;
		}
		mid=(low+high)/2;
	}
	if(max==ans[0]) return 0;
   	else return max;	
}

int solve(int num)
{
	int i,len,j,max;
	len=1;
	ans[0]=MIN;
	ans[1]=shuru[1];
	left[1]=1;
	for(i=2;i<=num;i++)
	{
		if(shuru[i]>ans[len])	ans[++len]=shuru[i];
		else
		{
			j=find(shuru[i],len);
			ans[j+1]=shuru[i];
		}
		left[i]=len;
//		printf("left[%d]=%d\n",i,left[i]);
	}

	len=1;
	ans[0]=MIN;
	ans[1]=nixu[1];
	right[1]=1;
	for(i=2;i<=num;i++)
	{
		if(nixu[i]>ans[len])	ans[++len]=nixu[i];//注意是>
		else
		{
			j=find(nixu[i],len);
			ans[j+1]=nixu[i];
		}
		right[i]=len;
//		printf("right[%d]=%d\n",i,right[i]);
	}
	max=0;
	for(i=1;i<=num;i++) 
	{
		if(left[i]+right[num-i+1]>max) max=left[i]+right[num-i+1];
	}
	return num-(max-1);
}


void print(int len)
{
	int i;
	printf("len=%d\n",len);
	for(i=1;i<=len;i++) printf("%d ",ans[i]);
	printf("\n");
}
int main()
{
	int i,num;
	while(scanf("%d",&num)!=EOF)
	{
		for(i=1;i<=num;i++) 
		{
			scanf("%d",&shuru[i]);
			nixu[num-i+1]=shuru[i];
		}
		printf("%d\n",solve(num));
	}
	return 0;
}