poj 1836 Alignment( 最長上升（下降）子序列 )

http://poj.org/problem?id=1836

題意：給n個士兵的身高，要求每個士兵向左或向右能看向無窮遠處(新隊列呈三角形分布)，最少要剔除幾個士兵；

思路：對數列分别順序，逆序求最長上升子序列，然後枚舉i和 j,使得以i結尾的上升子序列與以j開頭的下降子序列的和最大；      

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	double a[1010];
	int dp_left[1010],dp_right[1010];
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
		scanf("%lf",&a[i]);
	//順序dp求上升子序列
	for(int i = 1; i <= n; i++)
	{
		dp_left[i] = 1;
		for(int j = 1; j < i; j++)
		{
			if(a[i] > a[j] && dp_left[i] < dp_left[j] +1)
				dp_left[i] = dp_left[j]+1;
		}
	}
	//逆序dp求下降子序列；
	for(int i = n; i >= 1; i--)
	{
		dp_right[i] = 1;
		for(int j = n; j > i; j--)
		{
			if(a[i] > a[j] && dp_right[i] < dp_right[j]+1)
				dp_right[i] = dp_right[j]+1;
		}
	}

	int ans = 0;
	//枚舉上升子序列的右端點和下降子序列的左端點；
	for(int i = 1; i < n; i++)
	{
		for(int j = i+1; j <= n; j++)
		{
			if(dp_left[i] + dp_right[j] > ans)
				ans = dp_left[i] + dp_right[j];
		}
	}
	printf("%d\n",n-ans);
	return 0;
}