poj 1836 Alignment (최 장 상승 (하강) 하위 시퀀스)

1184 단어 dp
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-ans); return 0; }

좋은 웹페이지 즐겨찾기