先正反推两次LIS，把结果保存下来，再枚举上升的终点和下降的起点得到最大的上升序列长度和下降序列长度之和



Source Code

Problem: 1836		User: AxePASS
Memory: 172K		Time: 0MS
Language: C++		Result: Accepted
Source Code
#include <cstdio>
#include <algorithm>

#define MAX 1000+10
using namespace std;

struct  
{
	int lis, lds;
} dp[MAX];

float fOrd[MAX];
float fSoldier[MAX];
int iNum;

void iLis ()
{
	//初始化数组
	for (int i = 0; i < iNum; i ++)
		fOrd[i] = 10.0;
	//记录序列长度
	int LEN = 0;
	for (int i = 0 ; i < iNum; i ++)
	{
		int temp1 = lower_bound(fOrd+1,fOrd+iNum+1,fSoldier[i])-fOrd;
		if (LEN < temp1)
			LEN = temp1;
		dp[i].lis = temp1;
		fOrd[temp1] = fSoldier[i];
	}

}

void iLds()
{
	//初始化数组
	for (int i = 0; i < iNum; i ++)
		fOrd[i] = 10.0;
	//记录序列长度
	int LEN = 0;
	//反着推，将下降序列转化为上升序列
	for (int i = iNum-1 ; i >= 0; i --)
	{	
		int temp2 = lower_bound(fOrd+1,fOrd+iNum+1,fSoldier[i])-fOrd;
		if (LEN < temp2)
			LEN = temp2;
		dp[i].lds = temp2;
		fOrd[temp2] = fSoldier[i];
	}
	
}

int main()
{
	while(~scanf("%d", &iNum))
	{
		
		for (int i = 0; i < iNum; i ++)
		{
			scanf ("%f", &fSoldier[i]);
		}
		memset(dp,0,sizeof(dp));
		iLis();
		iLds();
		int max = 0;
		for (int i = 0; i < iNum-1; i ++)
			for (int j = i + 1; j < iNum; j ++)
				if (max < dp[j].lds+dp[i].lis)
					max = dp[j].lds+dp[i].lis;


		printf("%d\n",iNum - max);
	}

}