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;
}

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

原文：http://blog.csdn.net/u013081425/article/details/19830293