POJ 1836-Alignment（DP/LIS变形）

Description

Input

Output

Sample Input

8
1.86 1.86 1.30621 2 1.4 1 1.97 2.2

Sample Output

4

最长上升子序列变形。

题意： 一排士兵，要求对于每个士兵。至少保证左边或者右边的人身高单调递增。问满足要求最少要出去多少人。这个问题等价于 最多有多少个士兵能够按要求排成一列。扫两遍LIS ，枚举每个点 求 max(dp_l[i]+dp_r[j]);i:1 to n; j:i+1 to n; 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define ll long long
#define maxn 116
#define pp pair<int,int>
#define INF 0x3f3f3f3f
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
int n,dp_l[1010],dp_r[1010];
double a[1010];
void solve()
{
	for(int i=2;i<=n;i++)
		for(int j=1;j<i;j++)
			if(a[i]>a[j]&&dp_l[i]<=dp_l[j])
				dp_l[i]=dp_l[j]+1;
	for(int i=n-1;i>=1;i--)
		for(int j=n;j>i;j--)
			if(a[i]>a[j]&&dp_r[i]<=dp_r[j])
				dp_r[i]=dp_r[j]+1;
	int ans=-INF;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		ans=max(ans,dp_l[i]+dp_r[j]);
	printf("%d\n",n-ans);
}
int main()
{
	while(~scanf("%d",&n))
	{
		for(int i=1;i<=n;i++)
		{
			dp_l[i]=1;
			dp_r[i]=1;
			scanf("%lf",&a[i]);
		}
		solve();
	}
	return 0;
}