poj 1836

是POJ2533的扩展题。题意不难，令到原队列的最少士兵出列后，使得新队列任意一个士兵都能看到左边或者右边的无穷远处。就是使新队列呈三角形分布就对了。士兵的排列就是如附件所示所示：图片中的蓝色士兵的身高和红色士兵的身高是完全没有关系的。

要求最少出列数，就是留队士兵人数最大，如图：

即左边的递增序列人数和右边的递减序列人数之和最大因而可转化为求“最长不降子序列”和“最长不升子序列”问题。进一步转化为从头部求出最长不下降子序列与从尾部求出最长不下降子序列即可，分别求出二者的大小，最后用队列长度减去二者之和就是我们所求的出列的士兵个数。

具体代码如下：

 

#include <iostream>
using namespace std ;
const int MAX = 1005 ;
double m[MAX] ;
int dp1[MAX] , dp2[MAX] ;
int main()
{
	// freopen( "e:\\in.txt" , "r" , stdin ) ;
	int n ;
	while ( cin >> n )
	{
		int i , j ;
		for ( i = 1 ; i <= n ; i++ ) 
		{
			cin >> m[i] ;
		}
		memset( dp1, 0,sizeof( dp1 ) ) ;
		memset( dp2, 0,sizeof( dp2 ) ) ;
		dp1[1] = 1 ;//从头开始计算最长的递增序列
		for ( i = 2 ; i <= n ; i++ )
		{
			dp1[i] = 1 ;
			for ( j = i-1 ; j >= 1 ; j-- )
			{
				if ( m[j] < m[i] && dp1[i] < dp1[j]+1 )
				{
					dp1[i] = dp1[j]+1 ;
				}
			}
		}
		dp2[n] = 1 ;//从尾部计算最长的递增序列
		for ( i = n-1 ; i >= 1 ; i-- )
		{
			dp2[i] = 1 ;
			for ( j = i+1 ; j <= n ; j++ )
			{
				if ( m[j] < m[i] && dp2[i] < dp2[j]+1 )
				{
					dp2[i] = dp2[j]+1 ;
				}
			}
		}
		int ans = dp1[n] ;//初始化ans
		for ( i = 1 ; i < n ; i++ )
		{
			for ( j = i+1 ; j <= n ; j++ )
			{
				if ( dp1[i] + dp2[j] > ans )
					ans = dp1[i] + dp2[j] ;
			}
		}
		cout << n-ans << endl ;
	}
	return 0 ;
}