합창대형【DP】

> Description N 명의 학생들이 한 줄로 서 있는데 음악 선생님은 그 중의 (N-K) 학생들을 불러서 나머지 K 명의 학생들을 합창 대형으로 만들어야 한다.합창대형은 이런 대형을 가리킨다. K명의 학우를 왼쪽에서 오른쪽으로 순서대로 번호가 1, 2..., K로 설정하면 그들의 키가 각각 T1, T2,..., TK로 설정하면 그들의 키는 T1을 만족시킨다...>TK(1<=i<=K).너의 임무는 모든 N명의 학우들의 키를 알고 있기 때문에 최소한 몇 명의 학우들이 줄을 서서 나머지 학우들을 합창 대형으로 배열할 수 있도록 계산하는 것이다.
> Input이 입력한 첫 번째 행은 전체 학생 수를 나타내는 정수 N(2<=N<=100)입니다.두 번째 줄에는 n개의 정수가 있고 빈칸으로 구분되며 i번째 정수인 Ti(130<=Ti<=230)는 i번째 학생의 키(센티미터)다.
> Output 출력은 한 줄을 포함하고 이 줄은 정수만 포함하며 최소한 몇 명의 학생이 줄을 서야 한다.
> Sample Input 8 186 186 150 200 160 130 197 220
> Sample Output 4
> 문제를 푸는 사고방식(코드가 매우 추하니 여러분은 보지 마세요)아니면 동적 기획으로 문제를 푸세요.사실 이 문제는 가장 긴 불하강 서열의 변형을 구하는 것으로 두 단락의 다른 방향으로 나뉜다.그리고 그것을 합치면 또 대머리가 되기 시작한다. 여기를 아주 오랫동안 조정했다.
> 코드

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=101;
int y,a[maxn],f[maxn][maxn],n,ans=maxn;
//y              ，a     ，f        ，ans     。
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	 scanf("%d",&a[i]);
	//   
	for(int k=1;k<=n;k++)
	//    ，n          （     ）
	{
		y=0;
		for(int i=1;i<=k;i++)
        {
        	for(int j=1;j<=i;j++)
		     if(a[j]<a[i]&&f[k][j]>f[k][i]) f[k][i]=f[k][j];
		    f[k][i]++;
        }//        （  ）
		for(int i=n;i>k;i--)
        {
        	for(int j=i+1;j<=n;j++)
		     if(a[j]<a[i]&&f[k][j]>f[k][i]) f[k][i]=f[k][j];
		    f[k][i]++;
		    if(f[k][i]>y&&a[i]<a[k]) y=f[k][i];
        }//        （  ）
        f[k][k]+=y;
        //           
		if(n-f[k][k]<ans) ans=n-f[k][k];
		//     
	}
	printf("%d",ans);
	return 0;
}