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

本文主要是介绍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( 最长上升（下降）子序列 )的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---